LeetCode-剑指68-I.二叉搜索树的最近公共祖先

1、深度遍历

我们可以利用一个函数确定待搜索的节点是否在当前节点构成的子树中。而后我们可以从根节点开始遍历：1、若两个节点同属于其左子树或右子树构成的节点，说明当前节点不是公共节点，我们移动至当前节点的左子节点或右子节点；2、若此时两个节点分属于不同的节点，说明当前的节点即为其最近公共祖先。

class Solution {
public:
    bool in(TreeNode *root, TreeNode *target) {
        if (!root) return false;
        if (root->val == target->val) return true;
        else if (root->val > target->val) return in(root->left, target);
        else return in(root->right, target);
    }

    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        TreeNode *res = root;
        while (res) {
            if (in(res->left, p) && in(res->left, q)) res = res->left;
            else if (in(res->right, p) && in(res->right, q)) res = res->right;
            else break;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2、深度遍历优化

我们可以对方法一进行优化，在一次遍历中查询当前节点是否为p和q的公共祖先：1、若当前节点的值等于p或q的值说明当前节点就是公共祖先；2、若当前节点的值大于或小于p和q的值则说明当前节点的左子节点或右子节点为其公共祖先；3、若不满足上述情况说明当前节点即为公共祖先。

class Solution {
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        if (root->val == p->val || root->val == q->val) return root;
        if (root->val > p->val && root->val > q->val) return lowestCommonAncestor(root->left, p, q);
        if (root->val < p->val && root->val < q->val) return lowestCommonAncestor(root->right, p, q);
        return root;
    }
};
1
2
3
4
5
6
7
8
9