二叉搜索树的最低公共祖先解释代码

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

二叉搜索树中 p 和 q 的 LCA 是距离根最远的 p 和 q 的共同祖先。

你的代码所做的是，你从上到下遍历，它遇到的第一个节点n的值在p和q之间，即p<q或与p或q之一相同，是p和q的LCA（假设p><q）。>

所以只需递归遍历 BST，如果节点的值都大于 p 和 q，那么我们的 LCA 位于节点的左侧，如果它小于 p 和 q，则 LCA 位于右侧。否则根是LCA（假设b和q都存在于BST中）