236.二叉树的最近公共祖先

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

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

示例 1：

img

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

Solution

236.png

递归思想就是，每次遍历到一个节点，就看他的左子树和右子树之中有没有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
class Solution {

    // 此方法用于找出二叉树中两个节点 p 和 q 的最低公共祖先。
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 基本情况：如果当前节点为空，或者当前节点是 p 或 q 中的一个，
        // 则返回当前节点。这表示找到了 p 或 q 中的一个，或者到达了叶子节点的末端。
        if (root == null || root == p || root == q) {
            return root;
        }

        // 递归在左子树中查找 p 和 q
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 递归在右子树中查找 p 和 q
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 如果在左子树中找到一个节点（p 或 q），在右子树中找到另一个节点，
        // 则当前的 root 是最低公共祖先。
        if (left != null && right != null) {
            return root;
        }

        // 如果左子树为空，那么根据 right 的值决定返回值；
        // 如果右子树为空，那么根据 left 的值决定返回值。
        // 如果 left 和 right 都不为空，由于已经返回 root，这行不会执行。
        return left != null ? left : right;
    }
}