去年刷二叉树专题的时候，卡在 LeetCode 1123 这道题上挺久的。题面翻译过来就一句话：给定一棵二叉树，返回它最深叶节点的最近公共祖先。句子越短，隐藏细节越多。很多朋友第一反应是“先找出所有最深叶子，再两两求最近公共祖先”，结果绕了远路。这道题的经典解法其实非常优雅——一趟后序遍历，每个节点同时返回“子树高度”和“当前子树里最深叶节点的最近公共祖先”两个信息，比较左右子树的高度就能一路收敛到答案。这篇文章把从读题到 AC 的完整思路写下来，包括我最初是怎么绕弯的、为什么高度比较能直接决定答案、两种实现各自踩过的坑，以及从这道题里提炼出的二叉树后序遍历通用套路。
1. 题意拆解：看起来一句话，实际有三个隐藏考点
1.1 什么才算“叶子”，什么才算“最深”
二叉树里的叶子节点定义很明确：左右孩子都为 null 的节点。但有一个容易被忽略的边界——如果整棵树只有一个根节点，它没有任何孩子，那它本身既是根也是叶子。这时候最深叶节点就是它自己，返回值也是它自己。
“最深”指的是深度最大，也就是离根节点路径最远。这里牵扯到一个初始化的细节：深度是从根节点算起的边数，还是节点数。如果根节点深度为 0，那叶子节点到根的路径有几条边，深度就是几；如果根节点深度为 1，那路径上经过几个节点，深度就是几。两种定义都能做题，但后续写递归时容易混淆，我习惯统一用“节点数”来理解，后面实现里叶子高度记为 1，空子树高度记为 0，这样递归出口和处理最省心。
还有一个容易搞错的点：最深叶节点不一定只有一个。完全二叉树的最底层所有叶子深度相同，它们都属于“最深叶节点”。这道题要处理的就是这一类多目标的情况，而不是简单找一个最深的节点。
1.2 最近的公共祖先可能是一个叶子本身
“最近公共祖先”这个概念在只有两个节点时很好理解，比如玩《王者荣耀》看技能树，两个英雄的天赋汇合到同一个前置节点，那个节点就是最近公共祖先。但当只有一个最深叶节点时，它没有“和其他叶子会合”的过程，它的最近公共祖先就是它自己。
举例来说，一颗单链树1 -> 2 -> 3，只有叶子 3 是唯一的叶子节点，最深叶节点就是 3，公共祖先自然是 3。很多人写代码时默认“祖先”一定要是某个中间节点，结果返回了 2 或者 1，那就完全错了。
再换一种理解方式：题目要求返回的其实不是“某个祖先”，而是“包含所有最深叶节点的最小子树的根节点”。如果最深叶子只有一个，这个最小子树退化成单节点；如果有多个，它就是从根开始、向下扩展到刚好包住所有最深叶子的那个分叉点。这个“最小子树根”的视角，对接下来的解法推导很有帮助。
1.3 用两个具体例子把答案钉死
第一个例子，也是 LeetCode 1123 自带的标准样例：
3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4深度按边数从根 3 算起：3 在深度 0，5 和 1 在深度 1，6、2、0、8 在深度 2，7 和 4 在深度 3。叶子节点有 6、7、4、0、8，其中深度最大的是 7 和 4，所以最深叶节点是这两个。它们俩往上会合的第一个公共节点是 2，因此返回值为节点 2，而不是更上层的 5，更不是根 3。
第二个例子，完全二叉树1, 2, 3, 4, 5, 6, 7：
1 / \ 2 3 / \ / \ 4 5 6 7四个叶子 4、5、6、7 都在最底层，深度相同。它们往上会合的第一个公共节点是根 1，所以返回值是根节点。这个例子特别能检验一个人是否真的理解了“公共祖先”的范围——如果返回了 2 或 3，说明只考虑了左子树或右子树最深叶子，没有意识到深度相同的叶子可能分布在两侧。
第三个例子，单链表形态的树1 -> 2 -> 3，唯一叶子是 3，返回 3。这个用例是专门用来防“返回中间节点”这个错误的。
2. 直觉推导：为什么比一比左右子树高度就能直接定答案
2.1 从根往下看，最深叶子一定偏向某一条分支
拿到一棵二叉树，站在任意一个节点上，左右两边各有一棵子树。如果左子树比右子树“深”，说明左子树里存在某个叶子，比右子树里任何叶子都离当前节点更远。那么整棵树的“最深叶节点”集合一定全部落在左子树里，右子树就算整个丢掉，也不影响最深叶节点是什么。
既然右子树里没有最深叶节点，那当前节点就不可能是“包含所有最深叶节点的最小子树”的根，因为答案完全可以在左子树内部找到，范围更小。于是我们带着问题下沉到左子树继续判断。
反过来，如果右子树更深，就下沉到右子树。只有当左右子树高度相等，说明两侧都各自存在同样深度的最深叶节点，也就是全局最深叶子既出现在左边，也出现在右边。取左边任何子树会漏掉右侧的叶子，取右边任何子树会漏掉左侧的叶子，唯一的公共覆盖点就是当前节点本身。
这一条推理是整道题的核心，比任何代码都重要。想通了它，后面写递归就是一马平川。
2.2 “高度相等”到底在哪个节点触发
这里高度指的是“以当前节点为根的子树内，最深叶子到当前节点经过的边数再加一”，等价于用节点数计的子树高度。叶子节点左右子树都为空，高度为 1；空子树高度为 0。
对任意节点 node，递归算出左子树高度 L 和右子树高度 R 之后：
- L > R：答案在左子树里，node 本身被淘汰；
- L < R：答案在右子树里，node 本身被淘汰；
- L == R：答案就是 node。
这个判断在做后序遍历时，天然可以逐层完成。因为后序遍历的顺序是先处理左右孩子，再处理当前节点，等到判断 node 时，左右子树的信息已经完全齐了。递归返回时，不仅要把“当前子树里最深叶节点的最近公共祖先”传回去，还要把“当前子树高度”传回去，因为父节点需要这两个信息才能继续做判断。
2.3 用族谱类比帮你记住它
想象一整个家族的族谱，现在要找到“最晚一代人的最近共同祖先”。最晚一代人如果都集中在某一支，那共同祖先一定在这支内部，往上追溯反而找错。如果最晚一代人在两个大分支里都有，那这两支分叉的那个祖先就是答案。
再换个更生活的类比：两个人分别从两座山脚往山顶爬，速度一样，最后要在一个汇合点碰面。如果左边的人起点更低（路程更长），那碰面点必然在左边那条路上；如果两边的路程一样长，碰面点就是两人刚开始分头走的那条路口。二叉树的”左右子树高度相等“，恰恰就是两条路一样长的路口。
3. 一次后序遍历的递归解法：返回值里同时装高度和答案
3.1 状态定义与递归公式
我定义一个递归函数dfs(node)，它返回两个信息：
- 以 node 为根的子树高度（叶子高度记为 1，空节点高度记为 0）；
- 这棵子树中所有最深叶节点的最近公共祖先。
递归分三种情况走：
- node 为 null，返回
(0, None)，空的子树谈不上叶子，也没有祖先； - 左子树更高，说明最深叶子全在左子树，答案取左子树返回的祖先，整体高度是左子树高度加 1；
- 右子树更高，说明最深叶子全在右子树，答案取右子树返回的祖先，整体高度是右子树高度加 1；
- 左右子树一样高，说明两侧都有最深叶子，答案就是 node 本身，整体高度是左子树高度加 1。
为什么高度要加 1？因为向上返回给父节点时，当前这层节点也算在路径里。这个加 1 的细节在写代码时很容易漏掉，漏掉后父节点的高度判断会整体少一层，导致该返回 root 的时候误返回子节点。
3.2 参考实现：Python 与 Java
Python 版本，用元组轻量返回两个值：
def lcaDeepestLeaves(self, root): def dfs(node): if not node: return (0, None) left_height, left_lca = dfs(node.left) right_height, right_lca = dfs(node.right) if left_height > right_height: return (left_height + 1, left_lca) if left_height < right_height: return (right_height + 1, right_lca) return (left_height + 1, node) return dfs(root)[1]Java 版本，用一个内部类封装结果：
class Solution { private class Result { TreeNode node; int height; Result(TreeNode node, int height) { this.node = node; this.height = height; } } public TreeNode lcaDeepestLeaves(TreeNode root) { return dfs(root).node; } private Result dfs(TreeNode cur) { if (cur == null) { return new Result(null, 0); } Result left = dfs(cur.left); Result right = dfs(cur.right); if (left.height > right.height) { return new Result(left.node, left.height + 1); } if (left.height < right.height) { return new Result(right.node, right.height + 1); } return new Result(cur, left.height + 1); } }代码量不大，但每一步都有明确含义。写的时候我建议把返回值格式写成注释，特别是团队协作或者自己两周后再回看时，不会忘记Result里两个字段到底代表什么。
3.3 手推一遍标准样例的递归过程
还是用3, 5, 1, 6, 2, 0, 8, null, null, 7, 4这棵树，我从最底层往上逐层推：
| 节点 | 左子树高度 | 右子树高度 | 返回（高度, LCA） |
|---|---|---|---|
| 7 | 0 | 0 | (1, 7) |
| 4 | 0 | 0 | (1, 4) |
| 2 | 1（来自7） | 1（来自4） | (2, 2) |
| 6 | 0 | 0 | (1, 6) |
| 5 | 1（来自6） | 2（来自2） | (3, 2) |
| 0 | 0 | 0 | (1, 0) |
| 8 | 0 | 0 | (1, 8) |
| 1 | 1（来自0） | 1（来自8） | (2, 1) |
| 3 | 3（来自5） | 2（来自1） | (4, 2) |
跟着这张表走一遍，能清楚看到答案是怎么从叶子 7、4 一路向上传导，最后停在 2。注意节点 1 也出现了左右高度相等的情况，返回的 LCA 是 1 自己，但那是子树内部的结论。到了根节点 3 这里，左边整体高度 3 大于右边整体高度 2，所以根节点直接采用左子树的答案 2，这也是正确答案，和标准输出完全一致。
3.4 为什么不用额外的全局变量
有朋友会问：能不能用一个全局变量记录最大深度，再在递归里动态更新答案？
理论上可以，但实现时非常容易出错。全局答案什么时候更新？碰到深度更大的叶子时更新一次，还是做完左右子树比较后更新？如果最深叶子分布在两侧，更新条件该怎么写？这些边界很难几句话讲清。相比之下，每个节点返回两个字段的写法是“纯函数式”的，不依赖外部状态，不会出现某个递归分支漏更新的问题。这也是工程里更推荐的做法——函数依赖越少，越不容易被调用顺序影响。
4. 备选方案：先给所有节点算好高度，再从上往下走
4.1 第一遍递归：用哈希表记录每个节点的高度
一次后序遍历不额外存储、直接返回答案，这是最优解。但如果有人第一次接触这道题，觉得“每个节点返回两个值”太抽象，可以先学两遍扫描版本，它更好理解。
第一遍用递归遍历整棵树，把每个节点的高度存进哈希表：
def lcaDeepestLeaves(root): height = {} def calc(node): if not node: return 0 left = calc(node.left) right = calc(node.right) height[node] = max(left, right) + 1 return height[node] calc(root)这里的height字典以节点对象为 key，每个节点被访问一次，记录的是以该节点为根的子树高度。叶子节点的高度为 1，空节点不进字典，后续取高度时直接用 0 兜底。
4.2 第二遍循环：从根开始向更高的一侧下沉
高度都算好之后，从头开始走一遍判断逻辑：
cur = root while cur: left_height = height.get(cur.left, 0) right_height = height.get(cur.right, 0) if left_height == right_height: return cur cur = cur.left if left_height > right_height else cur.right return None这一遍循环其实和一次 DFS 里的判断完全一样：哪边高往哪边走，两边一样高就返回当前节点。区别只是判断时点不同——一次 DFS 是在递归返回过程中顺势完成，这里的写法是把所有高度先算完，再“重新走一遍”树。
4.3 两种方案的对比
| 方案 | 遍历次数 | 额外空间复杂度 | 代码量 | 理解难度 |
|---|---|---|---|---|
| 一次后序遍历 + 返回双值 | 1 | O(h)，h 为树高 | 短 | 中等 |
| 两遍扫描 + 哈希表 | 2 | O(n)，n 为节点数 | 稍长 | 较低 |
时间上两个方案都是 O(n)，每个节点只有常数次操作。但两遍扫描有两点劣势：一是需要额外的 O(n) 空间存哈希表，二是第二遍循环时依赖第一遍已经算好的数据，如果某个节点高度取错，错误会被悄悄放大。第一遍算高度时用max(left, right) + 1，第二遍如果直接调height.get(cur.left, 0)，两者必须保证定义一致，这个一致性是很容易被忽略的坑。
另外，务必不要写出第二遍重新递归计算子树高度的版本。那样每个节点在不同路径上会被重复访问多次，时间复杂度会退化到 O(n^2)，在大树上基本跑不过测试数据。
5. 实测中容易踩的坑：从空指针到递归爆炸
5.1 高度定义不统一，代码前后打架
我在 1.1 说过，深度的定义有两种口径。写代码时我强烈建议以“空节点高度为 0、叶子高度为 1”作为唯一标准。因为很多题目默认空节点返回 0，比如 LeetCode 110 平衡二叉树、543 二叉树的直径，统一口径之后在几道题之间切换不容易出错。
如果你非要用“叶子高度为 0、空节点高度为 -1”，逻辑上也能 AC，但两个分支的高度之差一旦出现负数，调试时非常折磨。实际写代码时我见过有人把left_height + 1写在外层，结果叶子节点返回 1，空节点返回 1，整棵树高度全错，答案自然跟着错。建议写完代码先跑一下“单节点树”和“叶子节点做根”的用例，能过滤掉大部分高度定义问题。
5.2 空树输入直接返回 null
有些实现会把答案初始化为 root，然后在递归里不停修改。空树输入时 root 本身就是 null，看起来没问题。但如果你用的是“返回双值”的写法：
dfs(null)返回(0, None)；- 外层取第二个字段，得到
None；
这是正确的空树处理。但有些写法是把答案引用的默认值设为 root，空树时经过某个判断分支返回了 null，而“非空树但只有一个分支”时又可能错误返回 null。建议在提交前显式测试根节点为 null 的用例，这类边界测试在面试中加印象分。
5.3 递归深度过大导致的栈溢出
LeetCode 上常规的二叉树测试数据不会太极端，但本地压测时我拿一条 5000 个节点组成的单链树跑 Python 递归，直接抛了 RecursionError。Python 默认递归深度限制是 1000 左右，Java 一般不会那么敏感，但同样存在栈帧占用。
遇到这种极端情况，最简单的应对是提高递归深度限制：
import sys sys.setrecursionlimit(1000000)不过这只是临时的解决问题方式，真正的工程环境里，更好的方案是把后序遍历改成迭代版本。迭代后序可以用栈模拟，配合记录每个节点的高度和候选 LCA，两种方案都能保住 O(n) 时间和 O(n) 空间。面试讨论算法思路时一般不用写迭代版本，但你要知道它有这个限制，并明确说出来。
5.4 和 LeetCode 865 的关系
LeetCode 865 题名是“Smallest Subtree with all the Deepest Nodes”，翻译过来就是“包含所有最深节点的最小子树”，和 1123 是完全同一道题。如果你在别的平台刷到 865，不用重新学，直接套用本文的解法即可。
我看过不少题解会用“先找出全局最大深度，再递归向下，遇到左右子节点中有更深叶子就继续走”的写法。这个思路也对，但它需要额外保存每个节点深度或者全局最大深度，编码细节更多。相比之下，一次 DFS 返回双值的写法，不需要知道全局最大深度是多少，属于无状态、更省心的方案。
5.5 验证用的三个核心用例
不管你用哪种写法，提交前先自测三个用例：
- 单节点
[1]，期望返回节点 1； - 单链
[1,2,3]，期望返回节点 3； - 完全二叉树
[1,2,3,4,5,6,7]，期望返回节点 1。
第三个用例如果答错，大概率是“只考虑了单侧最深叶子”或者“递归比较高度写反了左右关系”。这三个用例覆盖了递归出口、单叶子答案、多叶子分叉三种核心情况，跑通了再交，基本不会出幺蛾子。
6. 从这道题抽出来的通用套路：一趟后序遍历回答一类问题
6.1 双值后序 DFS 的适用范围
LeetCode 1123 给我最大的收获，不是记住了这一道题的题解，而是掌握了一个“后序遍历返回多种统计信息”的思考框架。凡是遇到“需要知道子树高度/深度/节点数，同时最终答案又依赖这些统计值”的二叉树问题，都可以套这个框架：
- LeetCode 110，平衡二叉树：递归返回子树高度，同时用一个全局或返回值判断左右高度差是否大于 1；
- LeetCode 543，二叉树的直径：后序遍历返回子树深度，沿途更新“左深度 + 右深度”的最大值作为直径；
- LeetCode 124，二叉树中的最大路径和：后序遍历返回“从当前节点向下的单边最大贡献”，同时更新全局最大路径值；
- LeetCode 236，二叉树的最近公共祖先：递归判断左右子树是否包含目标节点。
这些题目看起来各不相同，底层的递归设计思路完全一样。每到一个节点，先从左右孩子拿到信息，再做一次判断，决定“向上返回什么”以及“是否更新答案”。
6.2 与 LeetCode 236 的判断逻辑对比
LeetCode 236 是在二叉树中找两个指定节点的最近公共祖先，它的判断条件通常是：
- 如果 node 等于 p 或 q，返回 node；
- 左子树递归结果非空、右子树递归结果非空，说明 p 和 q 分居两侧，node 就是答案。
LeetCode 1123 的判断条件更简单：
- 左子树高度等于右子树高度，node 就是答案。
一个是“布尔条件判断”，一个是“数值比较判断”，但递归下沉的骨架一模一样。刷完这道题之后，再回头去刷 236 会轻松很多，因为树形递归的返回值设计已经内化成肌肉记忆了。
6.3 写这类递归的四步心法
我总结了一套四步法，每次写树形递归都按这个顺序来：
- 先决定函数返回什么。宁愿多返回一个字段，也不要少返回。比如这道题，如果想只返回祖先节点，父节点就没法判断左右谁更深；只返回高度，就没法把祖先信息向上传递。“返回祖先 + 返回高度”是解决这类题的最小完整集合。
- 先写递归出口。空节点返回什么，要提前想好。这道题是
(0, None)。 - 再写递归主体。分别拿到左右子树的结果，做一个 if-else 判断。判断时大脑里要有一个具体样例，不要凭空写。
- 自测用例。单节点、双节点、完全二叉树、单链，这几类用例能在 30 秒内发现 80% 的错误。
我个人在实际刷题中的体会是，算法题树形递归的难点不在“递归”本身，而在“状态传递”。每次写递归前，我都会问自己两个问题：当前节点能从子树拿到什么信息？父节点需要从我这里拿到什么信息？把这两个问题想清楚，代码基本就出来了。LeetCode 1123 就是这个思维方式的绝佳训练场，值得多写几遍，甚至可以把三种解法都实现一遍，对比它们的内存消耗和代码风格差异。刷到后面你会发现，这种“双值返回值”设计在二叉树系列题目中反复出现，一旦熟练掌握，再遇到类似题目就不需要看题解了。
