去年刷二叉树专题的时候卡在 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 在深度 05 和 1 在深度 16、2、0、8 在深度 27 和 4 在深度 3。叶子节点有 6、7、4、0、8其中深度最大的是 7 和 4所以最深叶节点是这两个。它们俩往上会合的第一个公共节点是 2因此返回值为节点 2而不是更上层的 5更不是根 3。第二个例子完全二叉树1, 2, 3, 4, 5, 6, 71 / \ 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 与 JavaPython 版本用元组轻量返回两个值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这棵树我从最底层往上逐层推节点左子树高度右子树高度返回高度, LCA700(1, 7)400(1, 4)21来自71来自4(2, 2)600(1, 6)51来自62来自2(3, 2)000(1, 0)800(1, 8)11来自01来自8(2, 1)33来自52来自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 两种方案的对比方案遍历次数额外空间复杂度代码量理解难度一次后序遍历 返回双值1O(h)h 为树高短中等两遍扫描 哈希表2O(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平衡二叉树递归返回子树高度同时用一个全局或返回值判断左右高度差是否大于 1LeetCode 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 就是这个思维方式的绝佳训练场值得多写几遍甚至可以把三种解法都实现一遍对比它们的内存消耗和代码风格差异。刷到后面你会发现这种“双值返回值”设计在二叉树系列题目中反复出现一旦熟练掌握再遇到类似题目就不需要看题解了。