LeetCode 236 二叉树的最近公共祖先：python3 题解

题目链接：236. 二叉树的最近公共祖先

目录

• 1. 题目理解
• 2. 解题思路分析
• 3. 解法一：递归法 (推荐)
  • 算法逻辑
  • 代码实现 (Python 3)
  • 图解递归过程
• 4. 解法二：存储父节点法 (迭代)
  • 算法逻辑
  • 代码实现 (Python 3)
• 5. 两种解法对比
• 6. 常见疑问解答 (FAQ)【⭐】
• 7. 总结

---

1. 题目理解

什么是“最近公共祖先” (Lowest Common Ancestor, LCA)？

想象一棵家谱树。对于两个人 p 和 q，他们的“公共祖先”是指一个人，这个人既是 p 的长辈（或自己），也是 q 的长辈（或自己），注意在这个定义里，自己可以是自己的祖先。而“最近”公共祖先，是指在所有公共祖先中，辈分最低（深度最深、离 p 和 q 最近）的那一位。

题目核心要求：
给定一个普通的二叉树（注意：不是二叉搜索树，节点值没有大小顺序），以及树中的两个节点 p 和 q，找到它们的最近公共祖先。

关键定义：

• 一个节点可以是它自己的祖先。
• p 和 q 一定存在于树中。
• p 和 q 不相同。

---

2. 解题思路分析

这道题主要有两种经典的解法：

1. 递归法（后序遍历）：最简洁、最常用，利用函数返回值传递信息。
2. 存储父节点法（迭代）：直观易懂，将树转换为“向上查找”的结构。

我们将重点讲解这两种方法。

---

3. 解法一：递归法 (推荐)

这是最优雅的解法。核心思想是自底向上的信息传递。

算法逻辑

我们定义一个递归函数 dfs(node)，它的任务是：在以 node 为根的子树中，寻找 p 或 q。

这个函数会有三种返回情况：

1. 返回 p 或 q：表示在子树中找到了 p 或 q 中的一个。
2. 返回 None：表示在子树中既没找到 p 也没找到 q。
3. 返回 最近公共祖先：表示 p 和 q 分别位于当前节点的左右两侧，当前节点就是 LCA。

递归步骤：

1. 终止条件：如果当前节点 root 为空，或者 root 就是 p 或 q，直接返回 root。
   • 为什么？ 如果找到了目标节点，就把它汇报上去。
2. 递归左右：分别在左子树和右子树中调用递归函数。
   • left = dfs(root.left)
   • right = dfs(root.right)
3. 判断结果：
   • 情况 A：如果 left 和 right 都不为空。说明 p 和 q 一个在左边，一个在右边。那么当前 root 就是最近公共祖先，返回 root。
   • 情况 B：如果 left 不为空，right 为空。说明 p 和 q 都在左子树里（或者左边找到了一个，右边没找到）。LCA 一定在左边，返回 left。
   • 情况 C：如果 right 不为空，left 为空。同理，返回 right。
   • 情况 D：如果都为空。说明这棵子树里没有 p 或 q，返回 None。

代码实现 (Python 3)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        使用递归（后序遍历）寻找最近公共祖先
        时间复杂度：O(N)，需要遍历所有节点
        空间复杂度：O(H)，递归栈的深度，H 为树的高度
        """
        
        # 定义递归辅助函数
        def dfs(node):
            # 1. 终止条件：
            # 如果节点为空，返回 None
            # 如果当前节点就是 p 或 q，返回当前节点（向上传递信号：我找到目标了）
            if not node or node == p or node == q:
                return node
            
            # 2. 递归处理左右子树
            left = dfs(node.left)
            right = dfs(node.right)
            
            # 3. 处理返回值
            # 如果左右子树都找到了目标（一个返回 p，一个返回 q）
            # 说明当前节点 node 就是分叉点，即最近公共祖先
            if left and right:
                return node
            
            # 如果只有一边找到了目标，那就把找到的那个结果继续向上传
            # 如果左边有结果，返回左边；否则返回右边（右边可能有结果，也可能都是 None）
            return left if left else right

        # 从根节点开始递归
        return dfs(root)

图解递归过程

假设树结构如下，找 p=5, q=4：

      3
     / \
    5   1
   / \
  6   2
     / \
    7   4 (q)
   (p)

1. 递归到节点 5 时，发现 node == p，返回节点 5。
2. 递归到节点 4 时，发现 node == q，返回节点 4。
3. 回溯到节点 2：
   • 左子树 (7) 返回 None。
   • 右子树 (4) 返回 4。
   • 节点 2 返回 4（把找到的信息向上传）。
4. 回溯到节点 5：
   • 左子树 (6) 返回 None。
   • 右子树 (2) 返回 4。
   • 关键点：此时节点 5 本身就是 p。根据代码逻辑 if not node or node == p or node == q: return node，它在第一步就直接返回了自己 5。
   • 修正理解：实际上，当递归进入 5 时，因为它匹配 p，直接返回 5。它的子树不会再被深入遍历（这是短路优化，但不影响结果正确性，因为如果 q 在 5 的子树里，5 本身就是 LCA）。
   • 最终，节点 3 的左边收到 5，右边收到 None（因为 1 那边没有 p 或 q）。3 返回 5。
   • 最终结果 5。

---

4. 解法二：存储父节点法 (迭代)

这种方法更符合直觉：先找到从根到 p 的路径，和从根到 q 的路径，然后找两条路径的最后一个公共节点。

由于题目给的节点没有指向父节点的指针，我们需要自己构建一个“子节点 -> 父节点”的映射表。

算法逻辑

1. 构建父节点映射：使用 BFS 或 DFS 遍历整棵树，用一个哈希表 parent_map 记录每个节点的父节点。parent_map[child] = parent。
2. 记录 p 的祖先链：从 p 开始，通过 parent_map 不断向上找父节点，直到根节点。将经过的所有节点存入一个集合 p_ancestors。
3. 查找 q 的祖先：从 q 开始，不断向上找父节点。遇到的第一个存在于 p_ancestors 集合中的节点，就是最近公共祖先。

代码实现 (Python 3)

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        使用父节点映射表 + 迭代查找
        时间复杂度：O(N)，遍历树构建映射 + 向上查找路径
        空间复杂度：O(N)，存储父节点映射和祖先集合
        """
        
        # 1. 构建父节点映射表 {子节点：父节点}
        # 使用栈进行 DFS 遍历，也可以用队列 BFS
        parent_map = {root: None}
        stack = [root]
        
        # 遍历直到找到 p 和 q 的父节点信息即可，但为了简单通常遍历完或找到两者为止
        # 这里为了代码简洁，我们遍历整棵树建立完整映射
        while stack:
            node = stack.pop()
            
            if node.left:
                parent_map[node.left] = node
                stack.append(node.left)
            
            if node.right:
                parent_map[node.right] = node
                stack.append(node.right)
        
        # 2. 记录 p 的所有祖先节点（包括 p 自己）
        p_ancestors = set()
        curr = p
        while curr:
            p_ancestors.add(curr)
            curr = parent_map[curr] # 向上移动
            
        # 3. 从 q 开始向上找，第一个在 p_ancestors 中的节点即为 LCA
        curr = q
        while curr:
            if curr in p_ancestors:
                return curr
            curr = parent_map[curr]
            
        return None # 理论上不会执行到这里，因为题目保证 p, q 存在

---

5. 两种解法对比

特性	解法一：递归法	解法二：父节点映射法
代码复杂度	低，代码非常短	中，需要额外构建哈希表
空间复杂度	O(H)，H 为树高 (递归栈)	O(N)，需要存储所有节点的父指针
时间复杂度	O(N)	O(N)
理解难度	较高 (需要理解递归返回值含义)	较低 (符合直觉的路径比较)
适用场景	面试首选，空间更优	树极深防止递归溢出，或需要多次查询 LCA 时

注意：对于 Python 而言，如果树退化成链表（深度 \(10^5\)），递归法可能会触发 RecursionError（最大递归深度限制）。虽然 LeetCode 通常调整了限制允许通过，但在实际工程中，解法二（迭代）更安全。但在算法面试中，解法一（递归）是标准答案。

---

6. 常见疑问解答 (FAQ)【⭐】

Q1: 为什么递归法中，如果 left 和 right 都有值，当前节点就是 LCA？
A: 因为 left 有值意味着左子树里包含了 p 或 q 中的一个，right 有值意味着右子树里包含了另一个。既然分居两侧，那么当前节点 root 必然是它们汇合的最低点。

Q2: 如果 p 是 q 的祖先（例如示例 2），递归法怎么处理？
A: 当递归遍历到 p 时，满足 node == p，直接返回 p。此时 p 的子树（包含 q）不会被继续深入递归。这个 p 会一路向上传递，直到根节点或其他分叉点。最终返回的就是 p。这符合定义（节点可以是自己的祖先）。

Q3: 为什么不用先判断 p 和 q 是否在树中？
A: 题目提示中明确说明了："p 和 q 均存在于给定的二叉树中”。所以不需要额外的检查步骤，简化了代码。

---

7. 总结

• 首选解法：递归后序遍历。它利用了二叉树的结构特性，代码最精简，空间效率最高。
• 核心技巧：理解递归函数的返回值不仅仅是“找到了”，而是“找到的那个节点（可能是目标，也可能是 LCA）”。
• 备选解法：如果担心递归深度溢出，或者需要多次查询不同节点的 LCA，可以使用父节点映射法。