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

题目描述

这是 LeetCode 上的 235. 二叉搜索树的最近公共祖先 ，难度为 中等。

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

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

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

示例 1:

1
2
3
4
5
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

输出: 6 

解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

1
2
3
4
5
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4

输出: 2

解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

DFS

也是常见的 LCA 问题，但相比 236. 二叉树的最近公共祖先，本题搜索对象为二叉搜索树，利用此特性，我们可以将搜索复杂度从 $O(n)$ 优化至 $O(h)$。

利用原函数作为递归函数，复用 root 作为搜索过程中的当前节点，根据 root 和两节点关系进行分情况讨论：

  • 若 root 为 p 和 q 中的任一节点：由于搜索过程是从上往下，因此 root 必然是距离两者垂直距离最远的最近公共祖先，返回 root；
  • 否则根据 root 和 p、q 的节点值大小进一步讨论，将 root 节点值记为 a，两节点值中的较小值记为 b，两节点中的较大值记为 c：
    • 若有 $b < a < c$，说明 p 和 q 中值较小的节点在当前节点 root 的左子树内，p 和 q 中值较大的节点在当前节点 root 的右子树内。由于搜索过程是从上往下，因此 root 作为首个满足该条件的节点，必然是距离两者垂直距离最远的最近公共祖先，返回 root；
    • 若有 $a < b$，说明两节点均在当前节点 root 的右子树内，递归处理 root.right；
    • 若有 $a > c$，说明两节点均在当前节点 root 的左子树内，递归处理 root.left。

Java 代码：

1
2
3
4
5
6
7
8
9
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q) return root;
        int a = root.val, b = Math.min(p.val, q.val), c = Math.max(p.val, q.val);
        if (a > b && a < c) return root;
        else if (a < b) return lowestCommonAncestor(root.right, p, q);
        else return lowestCommonAncestor(root.left, p, q);
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == p || root == q) return root;
        int a = root->val, b = min(p->val, q->val), c = max(p->val, q->val);
        if (a > b && a < c) return root;    
        else if (a < b) return lowestCommonAncestor(root->right, p, q);    
        else return lowestCommonAncestor(root->left, p, q);
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root == p or root == q:
            return root
        a, b = root.val, min(p.val, q.val)
        c = max(p.val, q.val)
        if a > b and a < c:
            return root
        elif a < b:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return self.lowestCommonAncestor(root.left, p, q)

TypeScript 代码：
1
2
3
4
5
6
7
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    if (root === p || root === q) return root;
    const a = root.val, b = Math.min(p.val, q.val), c = Math.max(p.val, q.val);
    if (a > b && a < c) return root;
    else if (a < b) return lowestCommonAncestor(root.right, p, q);
    else return lowestCommonAncestor(root.left, p, q);
};

  • 时间复杂度：$O(h)$，其中 $h$ 为二叉搜索树的深度
  • 空间复杂度：$O(h)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.235 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。