二叉树最低公共祖先（LCA）详解：递归与迭代全面吃透

刷 LeetCode 的热门 100 题时二叉树这一块基本是绕不开的而第 236 题 Lowest Common Ancestor of a Binary Tree二叉树的最低公共祖先又是里面非常经典的一道。这题不光是面试高频更重要的是它背后那种“自底向上”处理树结构的思想一旦想通了你对递归、对树的遍历顺序都会有一个全新的理解。今天我就把这题的题目含义、几种主流解法、代码实现细节以及我实际刷题过程中踩过的坑全部展开聊聊希望能帮你一次吃透。先说这题到底在问什么给定一棵二叉树和两个节点 p、q要你找出这两个节点在这棵树里的最低公共祖先。所谓公共祖先就是同时包含 p 和 q 作为子节点的祖先节点“最低”则要求这个祖先离 p 和 q 尽量近。换句话说你要找的是 p 和 q 在树上往上走的“第一个交汇点”。这个定义看似简单真上手做的时候很多人在“递归返回什么”“左右子树的结果怎么合并”这些地方容易卡住。适合看这篇的人我觉得有两类一类是刚开始刷树的题目、对递归还不太熟的新手另一类是已经能 AC 这题、但想了解更多解法细节和面试扩展的同学。我会把从暴力思路到最优递归、再到迭代实现的完整链路都拆开讲让大家不仅会写代码更明白每一步为什么要这么写。1. 题目理解与解法选型先想清楚“公共祖先”到底是什么1.1 这道题的本质是找“分叉点”我一开始做这题时第一个直觉是从根节点出发分别找到通往 p 和 q 的路径然后比较这两条路径最后一个相同的节点不就是公共祖先吗这个思路非常直观也是很多教科书上给出的解法。但问题在于如果每次查询都去完整地扫描整棵树、再对比路径效率不够理想而且代码写起来会有一段额外的路径存储逻辑。后来我换了个角度公共祖先本质上就是 p 和 q 在树上“分道扬镳”之前的那个节点。想象一下如果 p 在根节点的左子树里q 在根节点的右子树里那么根节点就是它们的公共祖先而且一定是最低公共祖先因为你再往下走、无论走左边还是右边都不可能同时包含两个节点了。这个观察非常关键它说明 LCA 的判断可以递归地完成去看当前节点的左子树和右子树里各自能不能找到 p 或 q如果两边都找到了那当前节点就是答案。这个思路的好处是你不需要显式地记录路径而是让递归天然地把信息从叶子节点往根节点传递也就是所谓的“自底向上”处理。树这个结构本身就有递归的特性所以用递归解树题是天然贴合的。我在刷题过程中最大的体会就是很多树相关的算法题只要把“后序遍历”用熟了思路就会清晰很多。1.2 三种主流解法的思路对比这道题能搜到的题解大概有三大类递归后序法、父指针迭代法、路径对比法。它们的核心思想、时间复杂度和适用场景都有差别我整理了一个小表格方便大家先有个整体认知解法核心思路时间复杂度空间复杂度适用场景递归后序法自底向上判断左右子树是否包含 p/qO(n)O(h)h 为树高递归栈最推荐代码简洁面试最常用父指针迭代法用哈希表记录每个节点的父节点再回溯O(n)O(n)需要查多次、且能改树结构/存额外信息时路径对比法找出根到 p、根到 q 的两条路径再对比O(n)O(n)思路最简单适合入门理解三种解法时间复杂度都是 O(n)因为无论如何最坏情况下都要访问整棵树才能确定公共祖先。但在实际面试和工程场景里递归后序法胜在简洁、不易出错所以我后续会详细展开这一种。另外两种我也会把完整代码和细节讲清楚因为你不知道面试官会不会追问“如果不让用递归怎么办”这时候迭代法就是很好的备选方案。1.3 为什么首选递归信息流才是关键有些同学看到“递归”两个字就头大总觉得递归难调试、容易栈溢出。但就这题而言递归恰恰是最贴合问题结构的方式。为什么因为树的定义本身就是递归的一棵树的左子树和右子树依然是一棵树。而 LCA 的判定又依赖左右子树的信息只有知道了左右子树里是否找到了 p 或 q才能判断当前节点是否就是答案。这种“先处理子问题再用子问题的结果推导父问题”的模式不就是后序遍历嘛。你不需要考虑整个树长什么样只需要想清楚一个节点上要做什么如果当前节点左子树有结果、右子树也有结果那就返回当前节点否则返回有结果的那一边。把这个逻辑递归地套到每个节点上整棵树的问题就自动解决了。这种思路一旦建立很多类似的问题都能套用比如“判断一棵树是否是平衡二叉树”“求二叉树的最大深度”本质上都是“后序遍历 返回值设计”的游戏。2. 递归解法从后序遍历说起2.1 核心代码与语义约定先直接给出一版比较标准的递归解法我用的是 Python 写法class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: # 终止条件空节点直接返回空如果当前节点是 p 或 q直接返回当前节点 if root is None or root p or root q: return root # 先递归处理左子树和右子树 left self.lowestCommonAncestor(root.left, p, q) right self.lowestCommonAncestor(root.right, p, q) # 如果左右返回值都不为空说明 p、q 分别出现在两个子树里 if left is not None and right is not None: return root # 哪边有结果就返回哪边 return left if left is not None else right这段代码很短但信息量非常大。关键在于你要理解这个递归函数返回值的“语义”。我约定的是递归函数lowestCommonAncestor(node, p, q)表示在node为根的这棵子树中能找到的 p 和 q 的最低公共祖先。如果在这棵子树中只找到了 p 或只找到了 q那返回的就是找到的那个节点本身。如果这棵子树里 p 和 q 都没找到就返回空。注意这个语义不是“找到 LCA 就只返回 LCA”而是“找到什么就返回什么”。很多同学写代码时在这里栽跟头总是想着“我只要 LCA”于是递归返回值设计得特别别扭。实际上你把语义放宽成“返回子树内找到的关键节点p/q/LCA”问题反而简单了。因为只有先把 p 和 q 都找到才能判断 LCA 在哪里。2.2 终止条件为什么这么写终止条件有三条判断root is None、root p、root q。很多人会问为什么当前节点是 p 或 q 的时候就能直接返回不用再往下递归了仔细想一下如果当前节点就是 p而 q 在 p 为根的子树里那么 p 就是 q 的祖先根据 LCA 的定义答案就是 p。这种情况下继续往下找是没有意义的因为就算在 p 的子树里找到了 q公共祖先也不可能比 p 更低了。反过来如果 q 不在 p 的子树里那返回 p 这个节点本身也是一种“找到了一个关键节点”的信号父节点拿到这个信号后自然能判断下一步怎么办。所以这个终止条件其实非常精妙它把“当前节点是目标节点”和“当前子树是空的”都当作了递归的出口。这样设计之后父节点只需要判断左右子树的返回值是否为空就能知道 p 和 q 被找到了几个、在哪里找到的。这是一层很典型的“返回值携带信息”的递归设计模式建议反复体会。2.3 左右子树的返回值到底代表什么递归代码写出来容易但很多人 debug 时看不懂结果就是因为没搞明白 left 和 right 这两个变量是什么样的状态。我再展开说明一下如果 left 不为空且 right 不为空说明 p 和 q 一个在左子树找到了、另一个在右子树找到了当前节点就是它们的“分叉点”也就是 LCA。如果 left 不为空但 right 为空说明这棵子树里只找到了 p 或 q 中的一个节点或者已经找到了 LCA那么把这个结果继续往上抛。如果 left 和 right 都为空说明这棵子树里啥也没找到返回 None 给上层。有人会担心如果 left 返回的是 LCAright 返回的是空那当前节点不会误判吗不会。因为当 left 已经返回了 LCA说明 p 和 q 都在左子树里意味着当前节点肯定不是 LCA真正的最低位在更下面。所以只需要把 left 这个结果继续向上传递即可。整个递归过程就像一层层“信息上报”每个节点把自己子树里的调查结果汇报给父节点父节点再做汇总判断。这个比喻我觉得比干讲代码好理解得多。2.4 一个关键边界情况p 是 q 的祖先这题有一个特别容易遗漏的边界情况p 本身就是 q 的祖先。比如树是3 / 5这样的结构p3q5。按照递归逻辑当调用lowestCommonAncestor(3, 3, 5)时第一步就会命中root p直接返回 3根本不会继续往下找 q。这个结果是对的因为 3 确实就是 3 和 5 的最低公共祖先。但很多同学第一次写的时候会在这一步犹豫“我还没找到 q 呢怎么就返回了”记住当当前节点是 p 时它往上传递的含义是“我在这里找到了 p”至于 q 到底在不在这个子树里其实不影响最终结果因为就算 q 在下面LCA 也是 p就算 q 不在下面那 p 和 q 肯定分散在 p 之上某个节点的两侧到那时父节点再拿这个 p 去和另一侧的 q 做合并就行。所以这里放心返回即可。3. 迭代解法用栈与父指针也能解3.1 父指针法一次遍历记录祖先链如果面试官说“限制不能用递归”那我们需要一个迭代版本。迭代解树的题通常用栈模拟递归过程这道题也不例外。一个比较常见的迭代思路是用 HashMap字典记录每个节点的父节点然后从 p 向上回溯祖先链再看 q 向上回溯时先遇到哪个 p 的祖先那个节点就是 LCA。代码可以这样写class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: # 用 dict 记录每个节点的父节点根节点的父节点记为 None parent {root: None} stack [root] # 一直遍历到同时找到 p 和 q 为止 while p not in parent or q not in parent: node stack.pop() if node.left: parent[node.left] node stack.append(node.left) if node.right: parent[node.right] node stack.append(node.right) # 先走一条链把 p 的所有祖先包括 p 自己放入集合 ancestors set() while p: ancestors.add(p) p parent[p] # 再走另一条链从 q 向上回溯第一个出现在集合中的节点就是 LCA while q not in ancestors: q parent[q] return q这个解法的优点是完全不使用递归逻辑也很清晰每一步都非常符合人的直觉先找到 p 和 q再顺着父指针往上找交汇点。缺点是需要额外的 O(n) 空间来存父指针关系。对于这个题来说n 是树节点数所以空间复杂度是 O(n)比递归的 O(h) 要大。但如果你面对的是“要在同一棵树上多次查询不同节点对 LCA”的场景父指针法其实可以复用一次性建立好所有节点的父指针之后每次查询都只要 O(h) 的时间回溯这就很划算了。3.2 路径法两条“家族谱系”对照另一种迭代/递归结合的思路是路径法分别找出从根节点到 p 的路径、从根节点到 q 的路径然后从两条路径的开头开始逐位比较最后一个相同的节点就是 LCA。这个思路最容易理解适合作为面试时的“思路热身”但代码写起来比前两种长一些。class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: def find_path(node, target, path): if not node: return False path.append(node) if node target: return True if find_path(node.left, target, path) or find_path(node.right, target, path): return True path.pop() return False path_p, path_q [], [] find_path(root, p, path_p) find_path(root, q, path_q) lca None for a, b in zip(path_p, path_q): if a ! b: break lca a return lca这段代码里最值得注意的就是find_path函数。它借助了“回溯”技巧先试着往左子树走如果找到了目标就一路返回 True找不到就把之前加入路径的节点弹出去再试右子树。这种“加入-试错-回退”的模式在很多树的路径问题中都会用到比如“求二叉树所有从根到叶子的路径”“求路径总和等于目标值的路径”建议你把它背下来、练熟属于万能模板。路径法的时间复杂度同样是 O(n)因为找两条路径本质上就是两次 DFS。空间方面要额外存两条路径最坏情况下 O(n)。整体来说它的优势在于“可解释性最强”劣势在于代码量和空间占用相对更大。我在实战中觉得如果只是对付面试递归后序法就够了但如果想把这题解彻底吃透路径法也必须会写。3.3 面试官视角如何根据场景选择解法我在给朋友做模拟面试时发现很多候选人能写出递归解法但一问“你的空间复杂度是多少”或者“如果不让用递归怎么办”就卡住了。这说明他们对解法背后的原理和取舍还停留在“背代码”阶段。这里我建议大家以面试官的视角来审视这道题如果面试官问的是“请实现一个函数找 LCA”通常期望你先给出递归后序法因为代码最简洁、最能体现对二叉树递归结构的理解。如果面试官追问“如果这棵树非常大递归栈很危险怎么办”你就要自然地切换到迭代父指针法并解释两者的空间复杂度差异。如果面试官继续谈“如果要在同一棵树上多次查询不同节点的 LCA怎么优化”那就进入父指针复用、甚至树上倍增等进阶话题了。当然236 题本身只要求单次查询能把父指针法讲清楚已经很加分。所以我的建议是这三种解法都要会写但不一定要在面试里全倒出来。先答最优、最简洁的递归法再根据面试官的追问逐步展开其他方案。这样既展示了深度又不显得挤牙膏。4. 常见坑位与刷题扩展4.1 节点值不唯一千万不要用 val 比较这个点我必须单独拎出来强调LeetCode 236 的 TreeNode 定义里每个节点有一个val但题目特意强调“p 和 q 是树中存在的节点”并且使用的是节点引用对象指针不是节点值。换句话说二叉树里可能出现两个不同节点、但val完全相同。如果你在代码里写root.val p.val这样的判断很可能拿到错误答案。正确做法是直接比较对象引用Python 里用is而不是。我前面给出的代码里写的是root p或直接root is p就是在强调这一点。Java 里则是比较引用root p。这一点搞错的话很容易出现“明明递归逻辑没问题结果就是不对”的情况。刷题时如果遇到这种“比较对象身份”的题目先检查有没有用成值比较这个坑我踩了不止一次。4.2 “两个节点一定存在”的前提假设236 题的描述中明确说了 p 和 q 是树中存在的节点这个前提非常重要。它保证了我们在递归过程中一定能同时找到两个节点也保证了父指针法里 while 循环不会死循环。但在真实面试里面试官可能会加个附加条件“如果 p 或 q 可能不存在于树中返回 null。”这时解法就需要调整了。最经典的改法是递归时不再只返回节点而是统计“当前子树里找到了几个目标节点”。比如自定义一个返回值(count, node)count 表示在该子树中找到了几个关键节点node 表示如果 count 达到 2 时找到的 LCA。如果最终 count 小于 2就说明至少有一个节点不在树中返回 None。这样既保持了递归结构又处理了额外的不确定情况。我建议大家在掌握基础版之后自己动手改造一下这个加强版对理解递归返回值的语义很有帮助。4.3 变体题二叉搜索树的 LCA 为什么更简单如果把题目从普通二叉树换成二叉搜索树BST就是 LeetCode 235 题。BST 有一个天然性质左子树所有节点的值都小于根节点右子树所有节点的值都大于根节点。利用这个性质LCA 的判断可以变得极其简洁class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: while root: if p.val root.val and q.val root.val: root root.left elif p.val root.val and q.val root.val: root root.right else: return root核心思想是如果 p 和 q 都在当前节点的左侧那么 LCA 一定在左子树里如果都在右侧则在右子树里如果 p 和 q 分别位于两侧、或者当前节点就是 p 或 q那当前节点就是 LCA。整个过程不需要递归也不需要额外空间时间复杂度 O(h)。这题我建议和 236 题一起刷对照着看能更清楚地理解“利用特殊结构”解决问题带来的优化。4.4 如果树的节点数巨大递归栈溢出的应对思路最后一个我想展开的是关于海量数据的场景。虽然 LeetCode 的测试数据不会大到让 Python 递归栈真实溢出但在工程实践中递归深度等于树高 h如果这棵树退化成长链h 等于 n递归栈可能就会被压爆。这时候除了改用迭代父指针法之外还有一种思路是“显式栈模拟后序递归”。也就是用栈手动模拟后序遍历的顺序同时记录每个节点的状态是否已经处理完左右子树本质上是把系统栈换成堆内存中的栈空间依旧 O(n)但可控性更强、不会发生栈溢出。这种做法代码会比较长面试中一般不会被要求手写但了解它的存在可以让你在谈论“可用性”“鲁棒性”时更有说服力。我个人的建议是先把递归版和父指针版吃透再去研究“显式栈模拟”作为进阶扩展。刷题不是一锤子买卖每道题多储备几种解法下次遇到类似的变体就不会慌了。写在最后关于 236 这道题我最大的体会是做树的题一定不要急着写代码先在纸上把“递归函数的返回值语义”定义清楚再想终止条件和合并逻辑。很多同学卡住不是因为代码能力不够而是没有想清楚子问题之间的信息是怎么传递的。另外建议你把后序递归模板和路径回溯模板都练熟这两种模式在树的题目里出现频率极高属于“一鱼多吃”的工具。我现在刷题时遇到树相关的问题第一反应基本都是试着用后序递归去解解不动了再想办法优化。236 题只是一个起点把这题琢磨透了再遇到“二叉树的最大路径和”“二叉树的最近公共祖先变体”之类的问题你会发现自己明显比以前更有底气。