给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。

p、q 为不同节点且均存在于给定的二叉搜索树中。

此树为二叉搜索树，我们可以很容易得到到达每个结点的路径

所以可以分别获取到达两个结点路径，然后寻找最后一次重复的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        if (root == NULL)
            return NULL;
        vector<TreeNode *> pathp;
        vector<TreeNode *> pathq;
        dfs(root, p, pathp);
        dfs(root, q, pathq);
        TreeNode *pre = NULL;
        for (int i = 0; i < pathp.size() && i < pathq.size(); i++) {
            if (pathp[i] == pathq[i])
                pre = pathp[i];
        }
        return pre;
    }

    void dfs(TreeNode *root, TreeNode *target, vector<TreeNode *> &path) {
        while (root != NULL) {
            path.push_back(root);
            if (root->val == target->val)
                break;
            if (target->val < root->val) {
                root = root->left;
            } else {
                root = root->right;
            }
        }
    }
};

因为是二叉搜索树，在搜索过程中，root与p和q的情况只有三种

root>p&&root>q 则pq都在root的左子树中

root<p&&root<q 则pq都在root的右子树中

root在p q中间则root为pq的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        while (root != NULL) {
            if (root->val > p->val && root->val > q->val)
                root = root->left;
            else if (root->val < p->val && root->val < q->val)
                root = root->right;
            else
                break;
        }
        return root;
    }
};

可以改成递归写法，root=root->left就是递归在左子树中寻找，

如果不是在搜索树中查找，直接在二叉树中寻找最近公共子祖先

那么我们需要分别在左子树右子树中同时寻找两个结点，并返回寻找结果left，right

如果其中一个为空则说明两个结点都在另一个子树上，

都不为空则说明两个结点一个在cur的左子树上，一个在右子树上，cur即是答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        if (root == NULL || root == p || root == q)
            return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);

        if (left == NULL)
            return right;
        if (right == NULL)
            return left;

        return root;
    }
};