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

题目链接（中等）

题目描述

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

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

数据范围：

• 树中节点数目在范围 [2, 10^5] 内
• -10^9 <= Node.val <= 10^9
• 所有 Node.val 互不相同
• p != q
• p 和 q 均存在于给定的二叉树中

示例

示例 1：

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

示例 2：

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

示例 3：

输入： root = [1,2], p = 1, q = 2
输出： 1

核心思路

最近公共祖先（LCA）：节点 x 是 p、q 的公共祖先，且深度尽可能大。

分类讨论：

• 如果 p、q 分别位于 x 的左右子树，那么 x 就是 LCA；
• 如果 x 本身就是 p 或 q，而另一个节点在 x 的子树中，那么 x 也是 LCA；
• 如果 p、q 都在同一侧子树，则 LCA 在那棵子树里，需要继续递归。

三种解法：

1. 递归（返回节点）：递归函数直接返回 LCA 节点，最优雅；
2. 递归（返回布尔值）：用辅助变量记录 LCA，思路像「找两侧各一个」；
3. 存储父节点：用哈希表记录每个节点的父节点，从 p 往上标记祖先，再从 q 往上找。

---

方法一：递归（直接返回 LCA 节点）✅ 推荐

思路及解法

定义递归函数 lowestCommonAncestor(root, p, q)，返回「以 root 为根的子树中，p 和 q 的 LCA」。

递归终止与返回：

• 若 root 为空：返回 None；
• 若 root == p 或 root == q：直接返回 root（找到了其中一个，它自己可能就是 LCA，或者它的祖先中会有另一侧凑齐）。

递归逻辑：

1. 递归左子树得到 left；
2. 递归右子树得到 right；
3. 判断：
   • left 和 right 都非空：说明左右子树各找到一个目标，root 就是 LCA，返回 root；
   • 只有 left 非空：说明两个目标都在左子树里，返回 left；
   • 只有 right 非空：同理返回 right。

直觉理解：

• 如果 p 和 q 在 root 的两侧，那么 left 和 right 都会返回非空，root 就是 LCA；
• 如果它们都在同一侧，那一侧的递归结果就是 LCA，另一侧返回 None，直接把这个结果「向上传递」。

代码极其简洁，只有几行，是面试中最常写的版本。

代码

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root is p or root is q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root

        return left or right

复杂度分析

• 时间复杂度：$O(n)$，每个节点访问一次。
• 空间复杂度：$O(n)$，递归栈深度最坏为 $n$（链状树）。

---

方法二：递归（返回布尔值 + 辅助变量）

思路及解法

定义 dfs(root) 返回「以 root 为根的子树中是否包含 p 或 q」（布尔值）。

递归过程：

1. 如果 root 为空，返回 False；
2. 递归左子树得到 lson；
3. 递归右子树得到 rson；
4. 判断 root 是否是 LCA：
   • lson && rson：左右子树各包含一个目标节点，root 就是 LCA；
   • root == p || root == q：root 本身就是其中一个目标，另一个在它子树中，root 也是 LCA；
5. 返回 lson || rson || root is p || root is q。

为什么找到 LCA 后，不会被更上层的祖先「抢答」？

因为找到 LCA 后，dfs(LCA) 只返回 True。更上层的祖先只会知道「子树里有目标」，但如果另一侧没有目标，就不满足 lson && rson，不会被误判为 LCA。

代码

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.ans = None
        def dfs(node: 'TreeNode') -> bool:
            if not node:
                return False
            lson = dfs(node.left)
            rson = dfs(node.right)
            if (lson and rson) or node is p or node is q:
                self.ans = node
            return lson or rson or node is p or node is q
        dfs(root)
        return self.ans

复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$，递归栈深度。

---

方法三：存储父节点（哈希表 + 向上跳）

思路及解法

核心思路：如果我们知道每个节点的父节点，就可以从 p 向上走到根，再从 q 向上走，找到第一个「两条路径的交点」，那就是 LCA。这和「两个链表找交点」是同一个套路。

流程：

1. DFS 建表：遍历整棵树，用哈希表 fa 记录每个节点的父节点；
2. 标记 p 的祖先：从 p 出发，一路往父节点走，把经过的节点记入 visited；
3. 从 q 往上找：从 q 出发，一路往父节点走，遇到的第一个在 visited 中的节点就是 LCA。

为什么是 LCA？

• visited 里存的是 p 的所有祖先；
• q 从自己往上走，遇到的第一个 p 的祖先，就是「同时是 p 和 q 的祖先」中离 q 最近的，即深度最大的公共祖先。

代码

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        fa = {root: None}

        # DFS 记录每个节点的父节点
        def dfs(node: 'TreeNode') -> None:
            if node.left:
                fa[node.left] = node
                dfs(node.left)
            if node.right:
                fa[node.right] = node
                dfs(node.right)

        dfs(root)

        # 从 p 往上标记所有祖先
        visited = set()
        while p:
            visited.add(p)
            p = fa[p]

        # 从 q 往上找第一个已访问的祖先
        while q:
            if q in visited:
                return q
            q = fa[q]

        return None

复杂度分析

• 时间复杂度：$O(n)$，DFS 遍历所有节点，之后 p、q 往上跳最多 $n$ 步。
• 空间复杂度：$O(n)$，哈希表 fa、集合 visited、递归栈各 $O(n)$。

---

关键细节

1. 方法一中「找到了就直接返回」

if not root or root is p or root is q:
    return root

• 如果 root == p，那么无论 q 在 root 的子树中还是在子树外，root 都是 LCA 的候选（要么就是 LCA 本身，要么它的祖先里会凑齐 q）；
• 直接把 root 返回给上一层，让上层来决定最终答案。

2. 方法一中 left and right 的判断

• 如果 left 和 right 都非空，说明左右子树各找到了一个目标，root 是唯一的 LCA；
• 如果只有一侧非空，说明两个目标都在那一侧，root 不是 LCA，把那一侧的结果向上传。

3. 方法二中为什么要用 self.ans

布尔返回值无法直接传递 LCA，需要用外部变量记录。因为 dfs 只返回「子树里有没有目标」，所以发现 LCA 时需要先存起来，再继续向上返回 True。

4. 用 is 还是 == 比较节点

题目保证所有 Node.val 互不相同，理论上 == 也可以。但 Python 的 TreeNode 默认没有实现 __eq__，所以 == 实际比较的是对象身份，和 is 等价。

从语义上讲，node is p 更明确，表示「是同一个节点对象」，推荐使用。

5. 三种方法的共同点

• 都是「自底向上」的思路：先递归到底部，再往回判断；
• 都利用了「p 和 q 分居两侧时，当前节点即 LCA」这个关键性质；
• 时间复杂度都是 $O(n)$，空间都是 $O(n)$。

---

总结

• LCA 的核心逻辑：p、q 分布在 x 的左右两侧，或 x 本身就是其中一个，则 x 是 LCA；
• 方法一（推荐）：
  • 递归返回 LCA 节点；
  • root 是 p 或 q 时直接返回 root；
  • 左右都非空则 root 是 LCA；
  • 否则返回非空的那一侧；
• 方法二：返回布尔值，用 self.ans 记录 LCA；
• 方法三：哈希表记父节点，从 p 往上标记，从 q 往上找交点；
• 三种方法时间都是 $O(n)$，空间都是 $O(n)$。

相关题目

• LC 235. 二叉搜索树的最近公共祖先（利用 BST 性质）
• LC 1644. 二叉树的最近公共祖先 II（p、q 可能不存在）
• LC 1650. 二叉树的最近公共祖先 III（带父指针）
• LC 1676. 二叉树的最近公共祖先 IV（多个节点）
• LC 1123. 最深叶节点的最近公共祖先（变形）