LeetCode 236 二叉树的最近公共祖先：python3 题解
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)# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val x# self.left None# self.right Noneclass 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# 如果只有一边找到了目标那就把找到的那个结果继续向上传# 如果左边有结果返回左边否则返回右边右边可能有结果也可能都是 Nonereturn left if left else right# 从根节点开始递归return dfs(root)图解递归过程假设树结构如下找p5,q43/ \5 1/ \6 2/ \7 4 (q)(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)class Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:使用父节点映射表 迭代查找时间复杂度O(N)遍历树构建映射 向上查找路径空间复杂度O(N)存储父节点映射和祖先集合# 1. 构建父节点映射表 {子节点父节点}# 使用栈进行 DFS 遍历也可以用队列 BFSparent_map {root: None}stack [root]# 遍历直到找到 p 和 q 的父节点信息即可但为了简单通常遍历完或找到两者为止# 这里为了代码简洁我们遍历整棵树建立完整映射while stack:node stack.pop()if node.left:parent_map[node.left] nodestack.append(node.left)if node.right:parent_map[node.right] nodestack.append(node.right)# 2. 记录 p 的所有祖先节点包括 p 自己p_ancestors set()curr pwhile curr:p_ancestors.add(curr)curr parent_map[curr] # 向上移动# 3. 从 q 开始向上找第一个在 p_ancestors 中的节点即为 LCAcurr qwhile curr:if curr in p_ancestors:return currcurr parent_map[curr]return None # 理论上不会执行到这里因为题目保证 p, q 存在5. 两种解法对比特性解法一递归法解法二父节点映射法代码复杂度低代码非常短中需要额外构建哈希表空间复杂度O(H)H 为树高 (递归栈)O(N)需要存储所有节点的父指针时间复杂度O(N)O(N)理解难度较高 (需要理解递归返回值含义)较低 (符合直觉的路径比较)适用场景面试首选空间更优树极深防止递归溢出或需要多次查询 LCA 时注意对于 Python 而言如果树退化成链表深度 105递归法可能会触发RecursionError最大递归深度限制。虽然 LeetCode 通常调整了限制允许通过但在实际工程中解法二迭代更安全。但在算法面试中解法一递归是标准答案。6. 常见疑问解答 (FAQ)【⭐】Q1: 为什么递归法中如果left和right都有值当前节点就是 LCAA: 因为left有值意味着左子树里包含了p或q中的一个right有值意味着右子树里包含了另一个。既然分居两侧那么当前节点root必然是它们汇合的最低点。Q2: 如果p是q的祖先例如示例 2递归法怎么处理A: 当递归遍历到p时满足node p直接返回p。此时p的子树包含q不会被继续深入递归。这个p会一路向上传递直到根节点或其他分叉点。最终返回的就是p。这符合定义节点可以是自己的祖先。Q3: 为什么不用先判断p和q是否在树中
