第一次做 LeetCode 865「具有所有最深节点的最小子树」的时候我一度被最小子树这四个字带偏了以为要去找节点数量最少的那个子树于是开始思考各种剪枝、统计节点数的方案。后来仔细一读题才发现这里的最小指的是在树结构上离根节点最远、但又恰好能覆盖所有最深节点的那棵子树。概念一旦理清解法其实并不复杂。这篇题解我打算从题目定义讲起把两种主流解法——后序遍历返回深度节点、以及哈希表记录父节点的层序解法——完整拆开最后聊聊这道题在面试和实际刷题中的价值。刷题前如果你对树的递归、后序遍历、最近公共祖先这些概念还需要巩固这篇文章也适合你从头看。目录如下先理解最深节点和最小子树到底在问什么再给出两种解法和详细代码然后分析复杂度与边界用例最后分享一些从这道题延伸出来的刷题心得。1. 先搞懂题面最深节点是什么答案节点为什么可能出现在中间层1.1 别把最小理解成节点个数最少题目里有一棵二叉树根的深度记为 0。假设树的高度是 h那么深度为 h 的那些节点就是最深节点。这里要额外强调一句所谓最深节点指的一定是叶子节点。因为只要一个节点还有孩子它的深度就小于整棵树的最大深度它就不可能是最深的节点。也就是说最深节点就是最深的那一层叶子。那包含所有最深节点的最小子树又怎么理解假设这棵树的最深层有 5 个叶子节点题目让你找一棵子树把这 5 个叶子全都包进去同时这棵子树的根要尽可能深——根越深子树覆盖的范围越小也就是通常意义上最小的子树。举一个很典型的例子如果最深的叶子恰好分散在根节点的左子树和右子树两侧那么这棵最小子树的根就只能是整棵树的根。但如果所有最深节点都集中在某一条路径的分支下那么答案可能是树中间的某个节点而根本轮不到根节点出场。这也是为什么不能简单地返回根节点。很多初学者会踩的坑在这里他们观察到最深层是树的底部就直接递归找最深叶子然后试图把最深的叶子节点作为子树根返回。这明显是不对的——单个最深叶子虽然包含所有最深节点如果只有一个最深节点时但叶子本身没有孩子它代表不了那棵覆盖所有最深节点的子树。所以题目的本质是要找到一个最高最深的、能覆盖最深层全部叶子的公共祖先节点。换句话说这个问题可以等价转换成求所有最深叶子节点的最近公共祖先LCA。1.2 从示例推导同样的题目不同的答案形态用题目自带的示例来验证这个理解。示例 1 的二叉树结构是[3,5,1,6,2,0,8,null,null,7,4]。可以画出这棵树根是 3左右孩子分别是 5 和 15 的孩子是 6 和 21 的孩子是 0 和 82 的孩子是 7 和 4。整棵树的最大深度是 3深度为 3 的节点是 7 和 4这两个叶子分别挂在 2 的左右两侧。要同时包含 7 和 4 的最小子树根就是它们的父节点 2。所以正确答案是 2 这棵子树。示例 3[0,1,3,null,2]也比较典型节点 0 的左孩子是 1右孩子是 3而 1 的右孩子是 2。最大深度是 2最深节点只有 2 这唯一一个叶子。因为只有一个最深节点包含它的最小子树就是节点 2 本身。这道题里如果你把答案理解成唯一最深节点的集合的最近公共祖先那么单个节点的 LCA 就是它自己逻辑完全自洽。看到这里你会发现题面虽然叫最小子树但回归到算法层面它考的就是最深叶集合的最近公共祖先。而求多个节点的 LCA经典做法无非两种要么自底向上递归判断左右子树哪个包含更深节点要么先找到所有最深节点再通过父指针向上收敛。接下来分别展开。2. 解法一后序遍历返回 (深度, 节点) 二元组一步到位2.1 为什么递归的返回值要设计成一个 pair这是整道题的核心思路。我们定义一个递归函数dfs(node)它返回两个信息以node为根的子树内部最深一层叶子的深度是多少以及当前这棵子树中包含所有最深叶子的最小子树的根节点是谁。用一个 pair 把这两个信息捆在一起返回是这道题最优雅的设计。因为对任意一个节点我们做判断时需要同时知道左右两边谁更深和深处那个节点的位置。如果只返回深度最后你仍然需要额外维护一个答案变量如果只返回节点你又无法判断两个子树谁包含更深的叶子。把两者一起返回递归的每一层都能独立完成决策不需要任何全局变量。空节点的返回值设计为{0, nullptr}是可以的。这么设定之后一个叶子节点会从两个空子树收到{0, nullptr}由于两边深度相等它就把自己当做答案返回同时深度变成1。这样叶子的深度就是 1父节点的深度自然累加。你也可以把空节点深度定义为 -1让叶子深度为 0两种约定都能跑通但一定要保证dfs的返回值与最终答案节点的对应关系正确。从我刷题的经验看空节点返回0的写法更不容易出错因为nullptr节点本身不会被访问到深度从 0 开始计数更直观。2.2 状态转移左右子树深度比较的三种情形对于当前节点node拿到左右两边的(depth, node)结果之后情况一共有三种左子树更深说明所有最深节点都在左子树里那么当前包含所有最深节点的最小子树就是左子树返回的那个答案节点整体深度加 1 向上传递。右子树更深逻辑完全对称答案节点来自右子树。左右子树一样深说明最深的叶子既出现在左边也出现在右边左右返回的节点各自覆盖不了对方的最深叶子那么能够同时覆盖左右两侧最深叶子的最近公共祖先只能是当前节点node本身。此时答案节点就是node深度加 1 继续向上传。这个状态转移最精妙的地方在于它不需要真正去比较叶子节点的位置只通过深度是否相等就能判断两侧是否都有最深节点。只要左右子树的最大深度相同就意味着树的最深层同时横跨两侧当前节点就必然是它们的最小公共祖先。如果你一开始没有往深度相等则当前节点是答案这个方向想很容易把问题复杂化。实际上树的递归题里比较左右子树的高度/深度是一个非常经典的判断模式后面我会专门再说。2.3 完整代码实现与细节说明下面给出 C 的实现。这个版本可以直接通过 LeetCode 的所有测试用例不需要借助任何全局变量。class Solution { public: TreeNode* subtreeWithAllDeepest(TreeNode* root) { return dfs(root).second; } pairint, TreeNode* dfs(TreeNode* node) { if (node nullptr) { return {0, nullptr}; } auto left dfs(node-left); auto right dfs(node-right); if (left.first right.first) { return {left.first 1, left.second}; } if (right.first left.first) { return {right.first 1, right.second}; } return {left.first 1, node}; } };有几个实现细节值得注意。第一dfs(root).second就是最终要求的子树根节点不需要额外维护答案变量。第二在左右深度相等时我直接返回node这是整个算法正确性的关键。第三如果树为空题目其实不会给这种输入但加上判空逻辑后代码的健壮性更好面试时也不会被问住。如果你更喜欢只用一次递归就返回节点而不是返回 pair其实也可以用全局变量记录当前深度最大值对应的答案节点。做法是先计算每个子树的最大深度在深度值更新时同步更新答案节点。但这种方法的问题是你依然需要两次后序遍历或者在后序遍历的同时记录高度写法反而不如 pair 版本干净。我个人在刷题时更推荐 pair 这种递归返回多维状态的思路因为它在很多树形 DP 题目里都能复用。3. 为什么后序遍历天然适合这道题公共祖先的等价视角3.1 解题本质就是求最深叶子集合的最近公共祖先前面提到过题目等价于求所有最深叶子的最近公共祖先。为什么要求 LCA而不是直接找最深的叶子因为最小子树必须同时覆盖所有最深节点如果最深节点有多个并且分散在不同分支那么答案必须往上走直到某个节点同时拥有这些最深叶子作为后代。这个往上走的终点就是所有最深叶子的最近公共祖先。举个例子理解假设某个家庭里最深的两条血脉分别来自爷爷的两个儿子。那覆盖这两支血脉的最小家庭单位就是这个爷爷而不是爷爷的父亲。放到二叉树上爷爷就是左右两个分支的最近公共祖先。树的深度越深公共祖先就离叶子越近公共祖先离叶子越近对应的子树就越小。这与题目要求的最小子树完美对应。很多题解会直接把这个题归类为二叉树最近公共祖先的变形题。这样归类是对的因为它的核心逻辑就是给定若干个节点最深叶子求它们的 LCA。只不过这里的若干个节点不是直接给你的而是需要通过层序遍历或深度计算先找出来。解法一的高明之处在于它把寻找最深节点和寻找公共祖先两个步骤合并到一次后序遍历里了。3.2 后序位置做判断的原因信息从子节点向上汇聚理解后序遍历为什么适合这个场景要从递归的调用顺序说起。二叉树的前序、中序、后序遍历分别对应着处理当前节点的三个时机进入节点时、处理完左子树后、处理完左右子树后。本题中我们要判断当前节点是不是所有最深叶子的公共祖先需要知道左右子树各自的情况——左子树最深节点的深度是多少右子树最深节点的深度是多少。这些信息只有等左右子树都递归完毕才能拿到所以判断逻辑必须写在后序位置即递归完left和right之后。这也是一个通用的方法论当树中某个节点的答案依赖其所有子节点的信息时就应当采用后序遍历自底向上地汇总。比如判断平衡二叉树、求二叉树直径、计算二叉树的最大路径和全部都是这个套路。如果你想用前序遍历强行从顶向下解决往往需要维护额外的状态参数代码会变得很别扭。3.3 常见误区递归返回的节点一定是子树根而不是某个叶子写这道题时很容易出现一种直觉反正最深节点在底部我让递归函数返回最深节点的指针不就行了这种思路在只有一个最深节点时确实能过一旦最深节点有多个返回单一叶子节点就会出错。所以一定要建立正确的抽象递归函数返回的是以当前节点为根的子树中满足题目要求的最小子树根节点。这个节点有可能是当前节点自身左右子树等深时也有可能是左子树或右子树递归返回的某个节点。另一个容易漏掉的细节是深度值到底代表什么。在返回 pair 的写法里depth并不是当前节点的层数而是以当前节点为根的子树中最深叶子的深度。一个空节点深度为 0叶子节点深度为 1。这样在父节点做比较时两个孩子的深度数值天然代表了两条分支能延伸到的最大深度。不少初学者在这里把当前节点本身的 depth和子树的最大深度搞混导致左右比较结果颠倒代码跑出来全是根节点。写递归之前先想清楚每一层状态的含义能帮你避开很多隐性 bug。4. 解法二哈希表记录父指针把复杂问题拆成两步4.1 第一步层序遍历找到所有最深叶子如果你觉得递归返回 pair 的思路有点绕那么哈希表 层序遍历的解法更符合直觉。它的思路是先通过层序遍历把每个节点的父节点记下来同时把最深层的那一批叶子全部收集到数组里然后用找多个节点最近公共祖先的模板方法统一处理。层序遍历找最深叶子非常直观用队列做 BFS每次遍历完整一层后把这一层的所有节点暂存下来。当队列为空时最后一次暂存的那一层就是最深的一层这些节点就是所有最深叶子。vectorTreeNode* cur; cur.push_back(root); while (!cur.empty()) { vectorTreeNode* nxt; for (TreeNode* node : cur) { if (node-left) { parent[node-left] node; nxt.push_back(node-left); } if (node-right) { parent[node-right] node; nxt.push_back(node-right); } } if (nxt.empty()) break; cur nxt; }这段代码结束后cur中的节点就是最深层的全部叶子节点同时parent哈希表记录了每个非根节点的父节点。需要注意如果整棵树只有一个节点nxt恒为空cur就是根节点自己后续的 LCA 收敛逻辑也要能处理这种单节点情况。4.2 第二步自底向上不断取父节点集合直到收敛为一个节点拿到最深叶子集合后怎么求它们的最近公共祖先一个简单而暴力的思路是把这些节点不停地替换成它们的父节点直到所有节点变成同一个节点。因为父节点集合的大小只会不断缩小最终一定收敛到某个公共祖先而这个最早收敛的节点自然是最近的公共祖先。while (cur.size() 1) { unordered_setTreeNode* unique; for (TreeNode* node : cur) { unique.insert(parent[node]); } cur.assign(unique.begin(), unique.end()); } return cur[0];这里用unordered_set去重是因为多个最深叶子可能有同一个父节点。去重之后cur变成当前层所有节点的父节点集合只要数量不是 1就继续向上。因为每次循环至少会让所有节点向上走一层所以循环最终一定会终止并且终止时cur[0]就是所有最深叶子的最近公共祖先。这种解法的优点在于思路清晰、几乎不需要动脑特别适合作为面试时的低保解法。它把问题拆成了两个最容易写的部分BFS 遍历找叶子 while 循环向上收敛。缺点是需要额外的哈希表存储父关系并且空间复杂度比纯递归高一些。如果题目数据量很大哈希表的开销可能会成为瓶颈但 LeetCode 给出的树规模通常不会触发这个问题。下面放一份完整的 C 实现class Solution { public: TreeNode* subtreeWithAllDeepest(TreeNode* root) { unordered_mapTreeNode*, TreeNode* parent; vectorTreeNode* cur; cur.push_back(root); while (!cur.empty()) { vectorTreeNode* nxt; for (TreeNode* node : cur) { if (node-left) { parent[node-left] node; nxt.push_back(node-left); } if (node-right) { parent[node-right] node; nxt.push_back(node-right); } } if (nxt.empty()) break; cur.swap(nxt); } while (cur.size() 1) { unordered_setTreeNode* unique; for (TreeNode* node : cur) { unique.insert(parent[node]); } cur.assign(unique.begin(), unique.end()); } return cur[0]; } };这里有个细节parent哈希表里没有根节点的记录但根节点不会进入内层 while 循环的parent[node]访问因为当cur还没有收敛到根节点的时候parent中必然能查到所有节点的父节点如果cur已经只剩根节点循环条件cur.size() 1已经不满足根本不会进入循环。所以不需要单独处理根节点的父节点为空的情况。4.3 两种解法的时空复杂度对比维度递归 pair 解法哈希表 层序解法时间复杂度O(n)每个节点访问一次O(n)BFS 遍历一次 向上收敛的总次数也是 O(n) 级别空间复杂度O(h)h 为树高递归栈开销O(n)哈希表、队列、集合都可能有 n 个元素思路难度稍高需要理解递归返回二元组的含义较低BFS 父指针思路直观代码量大约 15 行大约 25 行偏好场景追求简洁与效率熟悉递归面试时希望快速给出可运行的方案两者的时间复杂度都是线性的差异主要在空间和代码风格。我自己通常优先写递归 pair 版本因为一次性后序遍历完事不额外开哈希表但如果面试官要求只能使用 BFS或者我怕递归层数过深导致栈溢出就会切换到哈希表版本。虽然题目给定的二叉树深度一般不会触发栈溢出但在工程化的项目中递归深度还是需要评估的。5. 复杂度、边界用例与刷题中的实际经验5.1 五类必测用例帮你快速验证解法正确性刷题时不能只在 LeetCode 上点提交拿到 AC 就觉得万事大吉。我习惯自己再构造几个边界用例验证解法的鲁棒性这里分享五类最有代表性的场景第一单节点树只有根节点。此时最深节点只有一个就是根节点整个树的最小子树就是根节点。递归版本中左右子树都为空深度相等返回node正确哈希表版本中cur只有根节点内层 while 不会执行也正确。第二完全对称的二叉树。比如一个满二叉树最深层叶子全部集中在最后一层且属于根节点的左右子树。此时答案必须是根节点因为最深叶子横跨两侧任何一侧子树都无法覆盖所有最深叶子。测试时可以和标准 LCA 的思路相互验证。第三最深层只有一个叶子。这种情况下答案就是这个叶子本身。如果树是链状的比如每个节点都只有一个右孩子那么最深的叶子在最底部答案也就是这个最底部的叶子节点。链状树同时可以用来测试递归深度会不会出问题。第四非对称树比如示例 3 那种[0,1,3,null,2]。最深节点是 2答案是 2 本身。这种用例用于验证程序是否能正确过滤掉父节点的另一侧子树深度不够的情况。第五所有最深叶子都集中在左子树但右子树有一定深度但不及最深。这种场景下答案应该在左子树内部而不是根节点。可以通过构造[3,5,1,6,2,0,8,null,null,7,4]的反向结构来测试。把这些用例都跑通后再提交到 LeetCode心里会踏实很多。5.2 面试现场怎么把这道题讲清楚如果面试官现场出这道题我建议按下面的节奏来答题既不啰嗦又能展示算法功底。第一步复述题意用自己的话解释最深节点和最小子树并说明这等价于求最深叶子的最近公共祖先。第二步给出最简单的暴力方案先层序遍历找最深叶子再逐个求 LCA得到正确答案后优化。这样即使最后没有写出最优解面试官也会看到你的分析过程。第三步写出后序遍历返回 pair 的递归解法重点解释左右子树深度相等时为何返回当前节点。这一句话其实就涵盖了整个题目的核心。第四步分析复杂度和边界条件。在讲解过程中注意把深度相等这个判断单独拿出来强调。很多面试官会追问为什么相等时当前节点一定是最近公共祖先你只要解释清楚如果左右子树的最大深度相同说明左右两侧都存在最深叶子而任何一侧子树都无法同时包含另一侧的最深叶子这个问题就答清楚了。还有一点加分项是提一下这道题和 LeetCode 236二叉树的最近公共祖先的关系两者在内核上是相通的。5.3 从 865 题延伸出去还该练哪些变形题刷完 865 之后有几道关联度很高的题值得趁热打铁。第一道是 LeetCode 236「二叉树的最近公共祖先」它和本题一样需要判断左右子树是否包含目标节点只不过目标节点是明确给出的而 865 的目标节点需要自己先找到。第二道是 LeetCode 543「二叉树的直径」它同样用后序遍历求左右子树深度之和但目的从找公共祖先变成了求最大路径长度思维转换很有意思。第三道是 LeetCode 110「平衡二叉树」它考察的是左右子树高度差也用到自底向上的信息汇聚只是返回值从 pair 变成了布尔值。第四道是 LeetCode 104「二叉树的最大深度」这是所有深度类题目的基础建议先把基础题吃透再上这种综合题。如果你希望挑战稍难的类似思路可以试试将问题扩展到多叉树一个节点有任意多个孩子求包含所有最深叶子节点的最小子树要怎么做核心思想不变但比较逻辑要从左右两棵子树变成遍历所有孩子、记录最大深度和第二大深度并判断多少个孩子达到最大深度。这种变形在面试中偶尔会出现提前想一想会比现场临时推理从容得多。最后分享一个我做这类题的个人经验拿到树的题目先不要急着写代码先在草稿纸上画一棵简单的树模拟几层递归返回的过程把每一层的(depth, node)的变化写出来。画三四个节点就能把规律看得很清楚。很多递归解法看起来难但只要动手模拟一次抽象的逻辑就会变得非常具体。865 这道题的核心就是比较左右子树的最大深度这个动作想明白这个动作整个题就通关了。
