二叉树最近公共祖先（LCA）详解：三种解法与面试扩展

1. 题目到底在问什么：最近公共祖先的直觉与定义

刷 LeetCode 的人迟早会遇到这道题：236. 二叉树的最近公共祖先。它在面试里出现的频率高到什么程度？我见过至少五家公司把原题搬进面试，有的是直接让你写，有的是换个皮考你——把二叉树换成多叉树，或者把节点换成带 parent 指针的版本。无论怎么换，核心都是同一个问题：给定一棵二叉树和两个节点 p、q，怎么找到离它们最近的公共祖先。

很多人看到“最近公共祖先”（Lowest Common Ancestor，简称 LCA）会先愣一下，其实用大白话说就是：p 和 q 往上看，往上走遇到的那个共同的“长辈”里，离它们俩最近的那个。注意“最近”这两个字，不是“最远”也不是“随便一个共同祖先”。整道题的难点就在这个“最近”上。

这道题适合谁来刷？如果你是刚学二叉树遍历的初学者，它能帮你把递归和遍历顺序真正想明白；如果你是准备面试的求职者，它几乎是一道必背模板题；如果你已经工作了，也可以用它来检验自己能不能把一个递归写得干净利落。我个人建议所有人都至少写出两种解法，因为面试官很爱追问“还有别的方法吗”。

1.1 先从一个最简单的例子说起

假设有这样一棵二叉树：

3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4

如果 p 是 6，q 是 2，那它们的公共祖先有 5 和 3，但最近的是 5。如果 p 是 5，q 是 4，那最近公共祖先就是 5 自己，因为 5 本身就是 4 的祖先。还有一种情况，p 和 q 一个在左边一个在右边，比如 6 和 0，那它们的最近公共祖先就是根节点 3。

用这个例子再去回看定义就清楚多了：公共祖先就是两个节点所在路径第一次交汇的地方。从 p 往上走到根，从 q 往上走到根，两条路径相交的第一个节点就是答案。

1.2 什么是“最近”，不是“最远”

这里有个容易绕的点：“最近”是从 p、q 往下看的视角，而不是从根往下看的视角。根节点一定是公共祖先，但往往不是最近的。很多初学者一上来会写一个“从根开始找”，结果发现找不到一个清晰的判定条件。

正确的思路是反过来的：与其从根往下找，不如从 p、q 往上找。可是二叉树并没有 parent 指针，怎么办？那就用递归去模拟“从下往上”的过程。这句话是整道题的关键。你先处理左右子树，再回头判断当前节点，这个顺序天然就是“从下往上”。

这也是为什么这道题几乎必然要跟后序遍历扯上关系。二叉树的遍历方式很多，先序、中序、后序、层序，这道题的核心解法里，递归版用的就是后序遍历的本质：左子树的结果、右子树的结果都有了，再决定当前节点是不是答案。

1.3 这道题为什么值得做

LeetCode 上这道题难度是中等，但它的含金量不低。首先是思路经典，它考察的是对树形结构递归的理解，而不是死记硬背模板；其次是扩展性强，改一改就能变成二叉搜索树的 LCA、多叉树的 LCA、带 parent 指针的 LCA；最后是细节多，比如 p 是 q 的祖先这种情况，很多人的代码能跑通但不一定能说清楚为什么。

我在不同的面试阶段遇到这道题时，写法都不一样。第一次刷题，我只会递归一种写法；后来为了讲清楚给别人听，我把哈希表、路径比较、带 parent 指针的写法都研究了一遍。你现在看到的这篇总结，就是我把这些方案按可读性和实用性重新整理后的结果。

2. 解法一：递归，从下往上的“认亲”逻辑

2.1 后序遍历才是本质

递归解法最精妙的地方在于，你不需要存储任何路径信息，只需要依赖函数调用栈，就能把“从下往上”这件事做了。思路是这样的：从根节点开始，去左子树找 p 或 q，去右子树找 p 或 q，如果两边都找到了，说明 p 和 q 分别位于当前节点的左右两侧，那当前节点就是最近公共祖先。

你可以把递归函数理解成一个“找亲戚”的过程。每个人问自己的孩子：你那边有没有我们要找的人？如果左子树说“我在左边找到了 6”，右子树说“我在右边找到了 0”，那当前节点就知道，自己就是那个连接两边亲戚的最近交汇点。

这个逻辑要求你用后序遍历的顺序来处理节点：先访问左子树，再访问右子树，最后处理当前节点。因为只有等你知道了左右两边的结果，才能做出判断。如果用先序遍历，你会在还不知道子树情况的时候就去判断当前节点，那是做不出正确结论的。

2.2 Python 实现与每一步解释

直接看代码：

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: # 空节点直接返回 None；当前节点等于 p 或 q 时，当前节点就是答案的一部分 if root is None or root == p or root == q: return root # 去左子树找 p 或 q left = self.lowestCommonAncestor(root.left, p, q) # 去右子树找 p 或 q right = self.lowestCommonAncestor(root.right, p, q) # 左右子树各自都找到了目标，说明当前节点是 LCA if left and right: return root # 只有一边找到，把找到的那边返回上去 return left if left else right

这段代码有两个关键点。

第一，递归出口为什么是root is None or root == p or root == q？因为如果当前节点已经等于 p 或 q，那它自己就是这条搜索路径上的一个“命中点”，不需要再往下找了。哪怕 p 和 q 是父子关系，比如 p 是 5，q 是 4，递归到 5 这一层时，root == p成立，直接返回 5，上层拿到这个结果就会知道已经找到其中一个目标了。

第二，left and right的判断为什么放在最后？因为函数调用栈的特性保证了这是一次后序遍历。当你在某个节点同时拿到 left 和 right 的返回值时，说明你已经把它的左子树和右子树都完整搜过了。这时候如果两边都非空，那当前节点就是左右两边目标的“分叉点”，也就是最近公共祖先。

2.3 为什么返回值可以这么设计

你可能会问，如果函数只返回 p 或 q，那怎么知道另一个目标在哪？答案在“分情况讨论”里。

情况一：递归到某个节点，左子树返回非空，右子树也返回非空，说明 p 和 q 一个在左一个在右，当前节点就是答案，于是返回 root。这个 root 会一路向上传递，直到最外层函数返回它。

情况二：只有左子树返回非空。这说明两个目标都在左子树里，或者，左子树里有一个目标，而另一个目标在更上层已经命中了。不管是哪种，当前节点都不是最近的交汇点，直接把左子树传上来的结果继续往上传就行。

情况三：左右都没有返回非空，说明这两个目标都不在以当前节点为根的子树里，返回 None 给上一层。

这三种情况合在一起，保证了每个节点只需 O(1) 的判断时间，整体复杂度是 O(N)。这个“返回值设计”是递归题里非常经典的手法：让子问题自己返回结果，父节点只做组合和判断。

2.4 递归解法的复杂度

时间上，每个节点最多被访问一次，所以是 O(N)，N 是二叉树的节点数。空间上，递归栈的深度等于二叉树的高度。如果是一棵平衡二叉树，高度约 O(log N)；如果是一棵退化成链的二叉树，高度是 O(N)。

这里我要多说一句，“树的高度”和你前面可能刷过的“二叉树的深度”是同一个概念。很多人在算这道题空间复杂度时会漏掉退化情况，写 O(1) 就交上去了，这在面试里是一个明显的减分项。面试官只要追问一句“如果树是链状的，空间是多少”，你就得答上来 O(N)。

3. 解法二：哈希表记录父节点，再向上找祖先链

3.1 思路：先建“父指针”，再做集合判重

递归解法虽然简洁，但有的同学第一次接触时很难理解“返回值到底是怎么组合的”。这时候哈希表解法就显得更直观：先遍历整棵树，把每个节点的 parent 记录下来，然后从 p 开始一路往上走，把经过的所有祖先记到一个集合里；再从 q 开始往上走，遇到的第一个出现在集合里的节点，就是最近公共祖先。

这个思路非常朴素，它模拟的就是“如果我有父指针，我会怎么做”。二叉树本身没有 parent 指针，但我们用哈希表手动造了一个映射：节点 -> 父节点。之后找祖先链就是纯粹的“顺着映射往上跳”。

我推荐这种方式作为第二解法，原因有二。一是它可读性强，代码逻辑几乎不需要脑补递归过程；二是它和你现实中解决问题的方式一致，遇到这类问题，先建索引再查询，很容易迁移到其他场景。

3.2 代码实现

class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: # 用栈做遍历，同时记录父节点 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 开始，把它的祖先链收集到集合里 ancestors = set() while p: ancestors.add(p) p = parent[p] # 从 q 往上走，遇到的第一个祖先就是答案 while q not in ancestors: q = parent[q] return q

这个写法里用的是栈，所以遍历方式是“先左后右”的深度优先遍历。你也可以换成队列做层序遍历，效果一样，因为我们的目标只是把每个节点的父节点记下来。

两个 while 循环需要解释一下。第一个循环为什么判断p not in parent or q not in parent？因为一旦 p 和 q 都出现在 parent 字典里，就说明我们已经找到了它们各自的位置，p 和 q 的父节点映射已经建立完毕，不需要再遍历整棵树了。这比无脑遍历完整棵树要省时间，尤其在 p、q 都靠近根节点时效果更明显。

第二个循环里，while p:会一路从 p 上跳到 root，再跳到 root 的父节点 None，然后结束。虽然 root 的 parent 是 None，但祖先集合里确实要包含 root 自己，所以这里用 while p 而不是 while parent[p] 是故意的。

3.3 什么时候用哈希表法更好

如果面试官要求你“不要递归，写一个迭代版本”，哈希表法是最容易想到的迭代方案。它的时间复杂度也是 O(N)，但额外空间比递归更直观：parent 字典最多存 N 个节点，ancestors 集合最多存树的高度个节点，所以空间复杂度 O(N)。

它的缺点也很明显：代码比递归长，而且要知道 p 和 q 一定在树里，否则 while 循环可能越界。不过在 LeetCode 236 的题目约束里，p 和 q 一定在当前二叉树中，你不需要处理“找不到”的情况。

从工程角度看，哈希表法其实更符合实际开发中的“以空间换时间”思路。当我们需要频繁查询同一棵树上不同节点对的 LCA 时，可以先预处理 parent 表，之后每次查询只要 O(H) 的时间，H 是树高。

4. 解法三：路径比较法，不用哈希表也能做

4.1 先找路径，再找分叉点

还有一种写起来也比较好理解的思路：找出从根节点到 p 的完整路径，再找出从根节点到 q 的完整路径，然后比较两条路径，从根开始往后数，最后一个相同的节点就是最近公共祖先。

举个例子。还是那棵树：

3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4

从根到 6 的路径是[3, 5, 6]，从根到 0 的路径是[3, 1, 0]。比较的时候，第一个节点都是 3，第二个节点分别是 5 和 1，从第二项开始就不一样了，所以最后一个相同节点是 3，LCA 就是 3。如果是从根到 7 的路径[3, 5, 2, 7]和从根到 4 的路径[3, 5, 2, 4]，前三个节点都一样，第四项不同，所以答案是 2。

这个方法的好处是，你不需要设计什么精巧的递归返回值，只需要会“找路径”和“比对路径”。找路径本身就是二叉树的遍历，正好把“二叉树的遍历”这个知识点练了一遍。

4.2 边界情况与代码细节

找路径的代码可以写成这样：

def find_path(root, target): path = [] def dfs(node): if not node: return False path.append(node) if node == target: return True if dfs(node.left) or dfs(node.right): return True path.pop() return False dfs(root) return path def lowestCommonAncestor(root, p, q): path_p = find_path(root, p) path_q = find_path(root, q) idx = 0 while idx < len(path_p) and idx < len(path_q) and path_p[idx] == path_q[idx]: idx += 1 return path_p[idx - 1]

细节主要在 dfs 里。递归进入 node 后，先把 node 加到 path 里；如果 node 就是目标，直接返回 True，不再往下走。如果左右子树都没能找到目标，就需要把 node 从 path 里弹出来，再返回 False。这样 path 里始终只保存“到达目标路径上的节点”，不会掺入已经回溯过的节点。

另一个细节是最后返回path_p[idx - 1]之前，要确保 idx 至少等于 1。题目保证 p 和 q 都在树里，所以两条路径至少有根节点这一个公共元素，idx 不会停在 0。

4.3 三种解法的横向对比

我用一张表总结三种解法，方便你记忆和面试时选型：

面试时，我一般先写递归，因为代码最短最优雅。如果面试官问“还有别的解法吗”，再补哈希表法。路径比较法可以作为备用，尤其是当你担心递归说不清楚的时候，用它兜底很安全。

5. 复杂度与边界，容易翻车的细节

5.1 递归栈空间的真实开销

很多人算递归空间复杂度时，会习惯性认为空间是 O(H)，H 是树高。这个结论本身没错，但你要能说清楚为什么。递归函数每次调用都会占用一个栈帧，栈帧里保存了当前参数和返回地址。在一条调用链上，同时存在的递归调用层数等于当前访问路径的深度。对一棵退化成链的树，深度就是节点数，所以空间是 O(N)。

这里顺带复习一下“二叉树的深度”这个概念。树的高度就是从根到最远叶子经过的节点数。刷题时经常能看到“求二叉树最大深度”的题，这和 LCA 的空间复杂度分析是连在一起的。你会求深度，就能分析递归栈上界。

如果担心递归栈溢出，你可以用显式栈的迭代写法。哈希表法本质上就是一个显式栈实现，它把系统栈换成了自己管理的栈，虽然空间复杂度没有降，但可控性更高。真实项目中，如果树特别深，我确实会偏迭代方案。

5.2 我踩过的几个坑

第一个坑：拿root == p or root == q作为出口时，没有考虑 p 是 q 祖先的情况。比如 p 是根节点，q 在左子树。递归到根节点时，第一层就直接返回 root 了，不会继续向下找。这其实是正确的，因为根节点就是 LCA。但如果你以为“必须两边都非空才能返回”，就会在这里卡住很久。

第二个坑：在递归返回值时，把left if left else right写反。注意，我们的目标是“把非空的那一边返回出去”。如果 left 为空，返回 right；如果 left 非空，返回 left。有些同学会写成right if left else left，结果刚好反了，当只有左子树命中时就返回了 None。

第三个坑：在哈希表法里，第一个 while 循环条件写成了while stack and (p not in parent or q not in parent)。其实不需要判断 stack，因为题目保证 p 和 q 一定在树里，遍历一定能找到它们。没必要多写这个条件，反而增加出错概率。

第四个坑：路径比较法里，找路径时没把已经访问过的节点从 path 中弹出。如果你忘写path.pop()，path 里会残留大量不在正确路径上的节点，最终比对结果自然错得离谱。这个 bug 特别隐蔽，因为小规模测试可能碰巧对，一旦树复杂一点就挂了。

5.3 快速避坑清单

• 递归出口建议写root is None or root == p or root == q，这三者顺序不能乱，先判 None，再做值比较。
• 只有在 left 和 right 都非空时，当前节点才是答案；否则继续上抛非空的那一侧。
• 哈希表法中 p 和 q 都出现在 parent 字典里后，就可以提前终止遍历，不需要等整棵树扫完。
• 路径比较法中，dfs 回溯时要 pop 干净，保持 path 只包含当前路径上的节点。
• 如果 p 是 q 的祖先，最终的 LCA 就是 p，面试时最好主动说出这个 corner case，能加分。

6. 面试扩展：从 LCA 能延伸出什么

6.1 如果题目变成二叉搜索树，一行迭代就出来

LeetCode 上有一道兄弟题：235. 二叉搜索树的最近公共祖先。它和 236 唯一的区别是，树是二叉搜索树，满足左子树所有节点值都小于根节点，右子树所有节点值都大于根节点。有了这个性质，你不需要递归找两边，只需要从根往下走，判断 p.val 和 q.val 与当前节点的关系。

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 一个比当前节点小、一个比当前节点大时，说明它们分布在当前节点两侧，当前节点就是最近公共祖先。如果两个都比当前节点小，就继续去左子树找；如果两个都比当前节点大，就去右子树找。这就是“搜索二叉树”带来的高效优化，时间可以压到 O(H)。

面试时如果你直接写 236 的通用解法，面试官反而可能提示你：还要考虑到这是二叉搜索树吗？所以看到题目里的搜索二叉树字样时，千万不要忽略这个条件。

6.2 多叉树/带父指针/多节点的 LCA

多叉树的最近公共祖先是一个很常见的变种。思路还是递归，只不过把 left 和 right 的判断改成遍历所有孩子节点。如果多于一个孩子返回了非空结果，那当前节点就是 LCA；如果一个都没返回，就返回 None；如果恰好一个，就返回那个结果。

带 parent 指针的解法则更偏向链表找交点。从 p 和 q 同时出发，每次各往上走一步，如果走到根就跳到另一个起始节点继续走，最终它们会在 LCA 处相遇。这个技巧在找两个链表交点时也常出现，值得你单独记忆。

还有一种题目是求多个节点的 LCA，比如“给一组节点的集合，求它们的最近公共祖先”。解法是把集合里的节点一个一个做 LCA 合并，或者利用递归计数，统计包含目标节点个数是否等于集合大小。两种方法都不难，但足以看出你对递归的理解深度。

6.3 LCA 与二叉树遍历、深度的关系

总结一下，这道题把“二叉树的遍历”“二叉树的深度”“二叉搜索树”“二叉树遍历”这几个热词全串起来了。递归解法和路径比较法分别用了后序和先序的遍历思路；空间复杂度分析要依赖树的深度；扩展开又跳到二叉搜索树的遍历优化。可以说，一道 LCA 学透了，二叉树的几个核心知识点等于同时复习了一遍。

我自己面试别人时，如果候选人能主动提到“这道题本质上是后序遍历，我可以把三种写法都写出来”，我基本就确定他的二叉树基础是扎实的。如果你只是背下来一个递归模板，建议再花点时间把哈希表法和路径比较法都自己敲一遍，写完之后你会有一种“原来如此”的顿悟感。

7. 常见问题与排查速查表

7.1 典型问题与解决方案

这份表格不是让你死记，而是当你在本地测试发现结果不对时，按表里的顺序做一次代码走查。我基本每次遇到“LCA 又写错了”的求助，最后都能归到上表中某一行。

7.2 本地测试时怎么构造样例

刷题平台会帮你判题，但本地调试时你需要自己搭树。很多人在 LeetCode 上提交错误后，想在本地复现，却苦于不会手动构造 TreeNode。我提供一个简单的方法：用列表层序建树，空节点用 None 占位。

def build_tree(values): if not values: return None root = TreeNode(values[0]) queue = [root] idx = 1 while idx < len(values): node = queue.pop(0) if values[idx] is not None: node.left = TreeNode(values[idx]) queue.append(node.left) idx += 1 if idx < len(values) and values[idx] is not None: node.right = TreeNode(values[idx]) queue.append(node.right) idx += 1 return root # 测试上一节那棵树 root = build_tree([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4]) p = root.left # 5 q = root.left.right.right # 4 print(lowestCommonAncestor(root, p, q).val) # 输出 5

构造好树之后，不要直接用数字 p=5 这种形式去调用，因为递归函数比较的是 TreeNode 对象引用，不是值。你需要通过树的节点引用去取 p 和 q，比如root.left、root.left.right。这个问题我见过至少三次，都是因为传入整型值而不是节点对象，导致永远走不到root == p or root == q这一分支。

测完常规例子后，建议你再测几个极端情况：p 是根节点、q 是根节点、p 和 q 是同一个节点、整棵树只有一个节点。这些边界用例能帮你快速定位递归出口的问题。

我个人的调试习惯是，在递归入口打印一下当前访问节点的 val，确认遍历顺序符合预期。LCA 这道题打印日志尤其有效，因为你能直观看到“左右子树返回值是怎么逐层向上传递的”。等代码终于跑通，再把打印删掉就行。

最后再分享一个小技巧：当你面对这道题感到脑子转不过来时，试试用一台真实的树形结构画图。拿纸笔或白板，把每个节点的左右子树返回值标注在旁边，整个递归过程一目了然。我们这行习惯说“递归是编译器的事”，但理解递归最好的方式永远是把自己当成那个递归函数，一步步往下走。做一次，胜过看十篇文章。