LeetCode 236. 最近公共祖先：树形递归的第一课

本站的算法题解系列已经走过了数组、字符串和链表，今天开一个新族：二叉树。第一道选最近公共祖先（Lowest Common Ancestor，简称 LCA），因为它是树形递归的分水岭——在它之前，树的题大多能用「处理当前节点 + 递归两个孩子」的套路糊过去；从它开始，你需要真正理解递归的返回值是什么、子问题的答案如何向上传播。这个模型在工程里的对应物也随处可见：git 找两个分支的合并基（merge-base）、面向对象语言解析菱形继承时找公共父类，本质上都在问同一个问题——这两个东西是从哪里分叉的。

题面与约束

给定一个二叉树，找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为：对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

约束条件：树中节点数在 2 到 10^5 之间；-10^9 <= Node.val <= 10^9；所有节点的值互不相同；p、q 为树中存在的不同节点。官方示例：树 [3,5,1,6,2,0,8,null,null,7,4] 中，5 和 1 的最近公共祖先是 3（根）；而 5 和 4 的最近公共祖先是 5 自己——最后这条「节点可以是自己的祖先」正是边界的关键约定。另外两条约束值得划重点：值互不相同（可以用值当身份，不用担心歧义）与 10^5 的规模（埋下了递归深度的伏笔，后面细说）。

定义里「深度尽可能大」这半句也值得咬文嚼字一下：p 和 q 的公共祖先有一整串（根节点永远是公共祖先），题目要的是其中最深的那一个。在树结构里这个答案天然唯一——两个节点在每一层至多共享一个祖先，深度越大候选越少，最后一个共享的祖先只有一个。这保证了算法返回单个节点是有意义的；换成 DAG（有向无环图）之后这个唯一性就没了，后文讲 git 时会回到这一点。

一个能做但笨的做法：先找路径再求交

最符合直觉的思路是模拟人类查家谱：分别找出根到 p 和根到 q 的两条路径，然后从头对齐比较，最后一个相同的节点就是答案。这个做法完全正确，很多题解也这么教，但它有两个不优雅之处：要维护两条路径的存储（每条最长 O(n)），要做一次额外的对齐比较，等于跑了三遍树。

更重要的是，它没有利用树形递归的本质。路径法把树当成图来遍历，而 LCA 有一个更贴近树结构的性质：答案就是「p 和 q 的搜索路径第一次分叉的那个节点」。分叉点以上的节点两条路径共享，以下的部分各自延伸——我们想找的就是那个共享段的最末节点。既然如此，为什么不把「找答案」交给递归的回程顺路完成？

后序递归：十行代码的传播逻辑

递归解法的状态定义可以写得非常短：lowestCommonAncestor(root, p, q) 返回「以 root 为根的子树中，p 和 q 的 LCA；若 p、q 不都在这棵子树里，返回找到的那个（或 null）」。转移只有三种情况：

• 当前节点为空，或者就是 p 或 q：直接返回自己——命中即止，不再往下找；
• 左右两边递归各拿一个结果：两边都非空，说明 p、q 分居两侧，当前节点就是分叉点，返回自己；
• 只有一边非空：p、q 都在同一边（或其中一个就是当前子树里的命中节点），把非空的那边向上传。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None or root is p or root is q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left is not None and right is not None:
            return root          # 左右各命中一个：当前节点是分叉点
        return left if left is not None else right

十行，每个节点访问一次，O(n) 时间。它的正确性值得停一步想清楚，因为有两处初学者最容易犯嘀咕。第一处：为什么「左右都非空」就能断定当前是 LCA？后序遍历保证递归调用返回时，左右子树各自的结果已经算完——两边都找到了命中，说明 p 和 q 分别藏在两侧子树里，而它们的任何共同祖先都必须同时是两侧的祖先，也就是从当前节点往上走，当前节点是满足条件的最深节点。第二处：p 是 q 的祖先怎么办？此时递归在 p 节点就提前返回了（命中即止），q 那一侧从头到尾不会产生结果，最终向上传播的一直是 p 自己——而 p 正是答案，「节点可以是自己的祖先」这条约定被天然覆盖。两个分支一并考虑，就没有漏掉的形状了。

递归的隐形陷阱：10^5 的链状树

这个解法在 C++ 和 Java 里可以直接提交通过，但在 Python 里藏着一个工程陷阱：Python 解释器默认的递归深度限制是 1000。题目的节点数上限是 10^5，出题人只要把树摆成一条向左的链，递归深度就是 10^5 层——裸交这份代码会直接 RecursionError 爆栈。

本文的代码在本地实测时就是这么做的：先建一条 10 万节点的链，把递归上限提到 30 万才让递归版跑通（sys.setrecursionlimit(300_000)）。但这只是练习环境的拐杖：递归深度抬高后，每次调用都要压一帧栈，10 万层的调用帧是实打实的内存开销。面试口头讨论时提一句「Python 里这道题的递归解有栈深度风险」，比背十个套路更能体现工程素养。要一份不依赖递归深度的实现，请看下一节。

迭代解法：一张父指针表

递归解法隐式利用的其实是调用栈，把栈换成自己管理的数据结构，思路立刻显形：如果每个节点都记着自己的父亲，那么 p 的祖先就是一条向上的链，q 也一样，两条链的第一个交点就是 LCA。

实现分三步。第一步，用显式栈做一次 DFS，为每个节点记下它的父节点（哈希表 parent，根的父亲记 None）；第二步，从 p 沿父指针一路走到根，把沿途所有节点（含 p 自己）扔进一个祖先集合；第三步，从 q 沿父指针向上走，第一个出现在集合里的节点就是答案——因为从 q 往上走是按深度递减的顺序，第一个命中的一定是最深的公共祖先。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        parent = {root: None}
        stack = [root]
        while stack:                       # 任意遍历顺序皆可，只为建 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)
        seen = set()
        cur = p
        while cur is not None:
            seen.add(cur)
            cur = parent[cur]
        cur = q
        while cur not in seen:
            cur = parent[cur]
        return cur

同样是 O(n) 时间、O(n) 空间，但全程没有一层函数递归。本文在本地用 10 万节点的链状树实测，迭代版跑完约 9 毫秒——同样的输入递归版需要先抬高递归上限才能不死。这个解法还有个额外的甜头：parent 表建完之后可以便宜地回答「任意节点的任意祖先」类问题，适合 LCA 查询不止一次的场景。

复杂度与常见疑问

两个版本的时空复杂度相同：时间 O(n)（每个节点最多被访问常数次），空间 O(n)（递归版是栈深度、迭代版是哈希表）。几个高频追问。问：如果题目不保证 p、q 一定在树里呢？（LeetCode 1644 就是这个变体。）命中即止的写法会把它误判成「祖先即答案」，需要把返回值升级成三元组——（LCA 候选，是否见过 p，是否见过 q），根节点汇合后再检查两个布尔标记。问：如果是二叉搜索树呢？（LeetCode 235。）有序性是可以兑现的折扣：p、q 都小于当前节点就往左走，都大于就往右走，第一次分居两侧的节点即答案，时间降到 O(h)、空间 O(1)——记得先利用性质，再套通用解。问：如果树节点自带 parent 指针呢？ 问题退化成「两条有公共尾部的链表求第一个交点」（LeetCode 160），双指针换轨法 O(1) 空间解决。问：同一棵树上要查非常多次 LCA 怎么办？ 每次 O(n) 就不够体面了，经典做法是预处理：倍增法给每个节点记下「向上 2 的幂次步」的祖先表，单次查询降到 O(log n)；Tarjan 的离线算法则借助并查集把全部查询批量处理。本题只问一次，O(n) 一趟就是最优，但「预处理换查询」的权衡思路值得放进工具箱。三问连起来正好说明：LCA 不是一道题，是一个随约束变化不断降档的问题族。

它在真实世界长什么样

LCA 是少数能直接对上工程名词的算法题。git 在合并两个分支时执行 merge-base，找的就是两条提交历史（DAG 里的两个节点）的最近公共祖先——找到它，才能确定「双方各自改了什么」；C++ 和 Python 处理菱形继承（两个子类继承同一个基类，又被一个孙类同时继承）时，方法解析顺序要找公共父类来决定查找路径；组织架构系统里「这两位员工的最低共同汇报人」、族谱软件里「这两位是几代以内的亲戚」，都是 LCA 换了层皮。区别只在数据结构：树换成 DAG 之后「最近」的定义会出现多个候选（git 为此专门定义了 best common ancestor），但「找分叉点」的心智模型不变。

举一反三

树形递归的心法同样可以压成一句话：先想清楚递归函数「返回什么」在什么意义上是对的，再让每个节点只做一次局部判断。LCA 的十行代码里，局部判断只有「左右是否都命中」一条——其余全部交给返回值的语义。这十行值得手写三遍。

参考资料

• LeetCode 236. Lowest Common Ancestor of a Binary Tree：原题与官方约束。
• doocs/leetcode：最近公共祖先多语言题解：社区维护的对照实现。
• Git 文档：merge-base：工程世界里 LCA 概念的对应物。
• Hello Interview：LCA 解法分析：面试视角的解法框架梳理。