Day120 | 灵神 | 二叉树 | 二叉搜索树的最近共公共祖先

235.二叉搜索树的最近共公共祖先

235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

思路：

二叉树的最近公共祖先【基础算法精讲 12】_哔哩哔哩_bilibili

可以先做一下236. 二叉树的最近公共祖先 - 力扣（LeetCode）

这道题是236的一种特殊情况

我们可以利用搜索树性质来查找q和p的最近公共祖先

还是分类讨论

1.如果q和p的值都是小于当前结点值的，那说明q和p肯定都在左子树，那他们的最近公共祖先肯定在左子树中

2.如果q和p的值都是大于当前结点值的，那说明q和p肯定都在右子树，那他们的最近公共祖先肯定在右子树中

3.如果不是以上两种情况，那只能是q和p分别在左右子树中，那么当前结点肯定是最近公共祖先了，就返回当前结点就行

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        int x = root->val;
        if (p->val < x && q->val < x) { // p 和 q 都在左子树
            return lowestCommonAncestor(root->left, p, q);
        }
        if (p->val > x && q->val > x) { // p 和 q 都在右子树
            return lowestCommonAncestor(root->right, p, q);
        }
        return root; // 其它
    }
};