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. 解题思路分析

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

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

我们将重点讲解这两种方法。
3. 解法一：递归法 (推荐)

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

我们定义一个递归函数 dfs(node)，它的任务是：在以 node 为根的子树中，寻找 p 或 q。
这个函数会有三种返回情况：

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

递归步骤：

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

代码实现 (Python 3)

1. # Definition for a binary tree node.
2. # class TreeNode:
3. #     def __init__(self, x):
4. #         self.val = x
5. #         self.left = None
6. #         self.right = None
8. class Solution:
9.     def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
10.         """
11.         使用递归（后序遍历）寻找最近公共祖先
12.         时间复杂度：O(N)，需要遍历所有节点
13.         空间复杂度：O(H)，递归栈的深度，H 为树的高度
14.         """
15.         
16.         # 定义递归辅助函数
17.         def dfs(node):
18.             # 1. 终止条件：
19.             # 如果节点为空，返回 None
20.             # 如果当前节点就是 p 或 q，返回当前节点（向上传递信号：我找到目标了）
21.             if not node or node == p or node == q:
22.                 return node
23.             
24.             # 2. 递归处理左右子树
25.             left = dfs(node.left)
26.             right = dfs(node.right)
27.             
28.             # 3. 处理返回值
29.             # 如果左右子树都找到了目标（一个返回 p，一个返回 q）
30.             # 说明当前节点 node 就是分叉点，即最近公共祖先
31.             if left and right:
32.                 return node
33.             
34.             # 如果只有一边找到了目标，那就把找到的那个结果继续向上传
35.             # 如果左边有结果，返回左边；否则返回右边（右边可能有结果，也可能都是 None）
36.             return left if left else right
38.         # 从根节点开始递归
39.         return dfs(root)

复制代码

图解递归过程

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

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

复制代码

• 递归到节点 5 时，发现 node == p，返回节点 5。
  
• 递归到节点 4 时，发现 node == q，返回节点 4。
  
• 回溯到节点 2：
  
  
  
  • 左子树 (7) 返回 None。
    
  • 右子树 (4) 返回 4。
    
  • 节点 2 返回 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 的路径，然后找两条路径的最后一个公共节点。
由于题目给的节点没有指向父节点的指针，我们需要自己构建一个“子节点 -> 父节点”的映射表。
算法逻辑

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

代码实现 (Python 3)

1. class Solution:
2.     def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
3.         """
4.         使用父节点映射表 + 迭代查找
5.         时间复杂度：O(N)，遍历树构建映射 + 向上查找路径
6.         空间复杂度：O(N)，存储父节点映射和祖先集合
7.         """
8.         
9.         # 1. 构建父节点映射表 {子节点：父节点}
10.         # 使用栈进行 DFS 遍历，也可以用队列 BFS
11.         parent_map = {root: None}
12.         stack = [root]
13.         
14.         # 遍历直到找到 p 和 q 的父节点信息即可，但为了简单通常遍历完或找到两者为止
15.         # 这里为了代码简洁，我们遍历整棵树建立完整映射
16.         while stack:
17.             node = stack.pop()
18.             
19.             if node.left:
20.                 parent_map[node.left] = node
21.                 stack.append(node.left)
22.             
23.             if node.right:
24.                 parent_map[node.right] = node
25.                 stack.append(node.right)
26.         
27.         # 2. 记录 p 的所有祖先节点（包括 p 自己）
28.         p_ancestors = set()
29.         curr = p
30.         while curr:
31.             p_ancestors.add(curr)
32.             curr = parent_map[curr] # 向上移动
33.             
34.         # 3. 从 q 开始向上找，第一个在 p_ancestors 中的节点即为 LCA
35.         curr = q
36.         while curr:
37.             if curr in p_ancestors:
38.                 return curr
39.             curr = parent_map[curr]
40.             
41.         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，可以使用父节点映射法。
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！