Самый низкий общий код объяснения предка для двоичного дерева поиска

Question

Я пришел к этой проблеме здесь, и я хочу, чтобы кто-то объяснил это решение, я не могу понять это.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { 
    while(root != NULL) { 
     if (p->val < root->val && q->val < root->val) { 
      root = root->left; 
     } else if (p->val > root->val && q->val > root->val) { 
      root = root->right; 
     } else { 
      return root; 
     } 
    } 
    return root; 
} 

Answer 1

Эксплуатационная Оценка р и д в бинарном дереве поиска является общим предком р и д, который расположен дальше всего от корня.

Что делает ваш код, вы пересекаете сверху вниз, первый узел n встречается со значением между p и q, т. Е. P < n < q или то же, что и один из p или q, является LCA от p и q (при условии, что p < q).

Так что просто рекурсивно пересекайте BST, если значение узла больше, чем p и q, то наша LCA лежит в левой части узла, если она меньше, чем p и q, тогда LCA лежит с правой стороны. В противном случае root является LCA (при условии, что оба p и q присутствуют в BST)