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

题目描述

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

百度百科中最近公共祖先的定义为：

对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先，并且 x 的深度尽可能大。

简单来说：

• x 必须同时是 p 和 q 的祖先

• 并且要离 p、q 尽可能近

• 也就是“最近”的那个公共祖先

示例分析

假设有这样一棵树：

示例 1

如果：

p = 5, q = 1

那么最近公共祖先就是：

3

因为：

• 3 是 5 的祖先

• 3 也是 1 的祖先

• 并且这是离它们最近的公共祖先

示例 2

如果：

p = 5, q = 4

那么最近公共祖先就是：

5

因为：

• 5 本身就是 p

• 同时 5 也是 4 的祖先

所以最近公共祖先可以是节点本身。

解题思路

这道题最经典的做法就是递归。

你给出的代码非常简洁：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q || root == null) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        if (left == null) return right;
        return left;
    }
}

虽然代码不长，但这道题的关键在于理解：

递归函数到底在返回什么。

只要把这一点想明白，这道题就非常顺了。

递归函数返回值表示什么

我们定义函数：

lowestCommonAncestor(root, p, q)

它的含义可以理解为：

在以 root 为根的这棵子树中，去寻找 p 和 q 的最近公共祖先，或者返回 p / q 中已经找到的那个节点。

换句话说，这个递归函数可能返回三类结果：

1. 返回 null 说明这棵子树里既没有 p，也没有 q

2. 返回 p 或 q 说明这棵子树里只找到了其中一个目标节点

3. 返回某个祖先节点 说明这棵子树里同时找到了 p 和 q，并且这个节点就是它们的最近公共祖先

为什么这题适合用递归

因为二叉树天然就适合拆成左右子树来处理。

对于当前节点 root，只需要问两个问题：

1. p 和 q 有没有出现在左子树里？

2. p 和 q 有没有出现在右子树里？

于是可以先递归去左边找，再递归去右边找。

最后根据左右两边的返回结果，判断当前节点是不是最近公共祖先。

这就是这道题的核心。

最关键的判断逻辑

递归处理完左右子树后，会得到：

TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);

然后分情况讨论。

情况 1：左右子树都找到了东西

也就是：

left != null && right != null

这说明什么？

说明：

• 左子树里找到了 p 或 q

• 右子树里也找到了 p 或 q

那就意味着 p 和 q 分别分布在当前节点的左右两边。

所以当前节点 root 一定就是它们的最近公共祖先。

于是直接返回：

return root;

情况 2：只有左子树找到了

也就是：

left != null && right == null

说明 p 和 q 都在左子树里，或者左子树里只找到了其中一个。

那最近公共祖先一定在左子树中，所以直接把左子树的结果往上返回：

return left;

情况 3：只有右子树找到了

同理：

left == null && right != null

说明答案在右子树里，直接返回：

return right;

情况 4：左右子树都没找到

也就是：

left == null && right == null

那当前整棵子树就没有目标节点，返回 null。

你的代码里这部分是通过：

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

自然覆盖掉的。

为什么递归终止条件这样写

代码最前面是：

if (root == p || root == q || root == null) return root;

这三种情况都可以直接返回。

1. root == null

说明走到空节点了，当然返回 null。

2. root == p

说明当前节点就是 p，那当前这棵子树已经找到一个目标节点了，直接返回 p。

3. root == q

同理，直接返回 q。

为什么找到 p 或 q 就直接返回

因为这道题找的是“最近公共祖先”。

如果当前节点就是 p 或 q，那么它本身就可能成为答案的一部分。

比如：

p = 5, q = 4

节点 5 本身就是 4 的祖先，所以答案就是 5。

因此，当递归碰到 p 或 q 时，不能继续往下找，而应该直接把这个节点返回给上层。

代码逐段解析

1. 终止条件

if (root == p || root == q || root == null) return root;

• 空节点返回 null

• 如果当前节点就是 p 或 q，直接返回当前节点

2. 递归搜索左右子树

TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);

去左右子树中分别查找目标节点。

3. 左右都不为空，说明当前节点是最近公共祖先

if (left != null && right != null) return root;

这是整道题最核心的一句。

4. 否则返回非空的那一边

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

• 如果左边没找到，就返回右边的结果

• 否则返回左边的结果

示例推演

还是看这棵树：

        3
      /   \
     5     1
    / \   / \
   6   2 0   8
      / \
     7   4

假设：

p = 5, q = 1

从根节点 3 开始

• 去左子树找：找到了 5

• 去右子树找：找到了 1

于是：

left != null && right != null

所以直接返回 3。

再看 p = 5, q = 4

从根节点 3 开始：

• 左子树里能找到 5

• 右子树里找不到 4

所以答案继续往左返回。

到了节点 5：

• 当前节点本身就是 p

• 直接返回 5

最终答案就是 5。

这也说明最近公共祖先可以是目标节点本身。

为什么不会返回更高层的祖先

很多同学第一次做这题时，会担心：

如果当前节点已经是公共祖先了，会不会上层节点又把它覆盖掉？

不会。

因为一旦某一层递归已经确定了最近公共祖先，它就会作为一个非空节点一路返回上去。

而更高层如果另一边是空，就只会继续返回这个结果，不会替换它。

只有当“左右两边分别找到目标节点”时，当前节点才会成为新的公共祖先。

而第一次满足这个条件的节点，恰恰就是“最近”的那个公共祖先。

复杂度分析

设二叉树有 n 个节点。

时间复杂度

O(n)

因为每个节点最多只会访问一次。

空间复杂度

O(h)

其中 h 是树的高度，主要来自递归调用栈。

• 平衡二叉树中，h = log n

• 最坏情况下，树退化成链表，h = n

这道题为什么这么经典

这道题是二叉树递归题中的代表题之一。

因为它非常适合训练下面这些能力：

1. 理解递归函数返回值的含义

2. 学会从左右子树的返回结果中整合答案

3. 处理“当前节点可能就是答案”的情况

4. 建立“后序遍历式递归思维”

很多二叉树题本质上都和这题很像：

• 先递归左右子树

• 再根据左右结果决定当前节点该返回什么

所以这题特别值得吃透。

总结

这道题的核心可以总结成三句话：

1. 如果当前节点为空，或者当前节点就是 p / q，直接返回当前节点

2. 递归去左右子树找 p 和 q

3. 如果左右子树各找到一个，当前节点就是最近公共祖先；否则返回非空的那一边

你可以把这题记成一句话：

最近公共祖先，就是第一个让 p 和 q 分别出现在它左右子树中的节点。

而递归写法正好可以非常自然地表达这个过程。