第一次做 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 和 1；5 的孩子是 6 和 2，1 的孩子是 0 和 8；2 的孩子是 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; } pair<int, 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，每次遍历完整一层后，把这一层的所有节点暂存下来。当队列为空时，最后一次暂存的那一层就是最深的一层，这些节点就是所有最深叶子。
vector<TreeNode*> cur; cur.push_back(root); while (!cur.empty()) { vector<TreeNode*> 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_set<TreeNode*> 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_map<TreeNode*, TreeNode*> parent; vector<TreeNode*> cur; cur.push_back(root); while (!cur.empty()) { vector<TreeNode*> 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_set<TreeNode*> 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 这道题的核心，就是"比较左右子树的最大深度"这个动作，想明白这个动作，整个题就通关了。
