第一次在LeetCode上刷到第310题“最小高度树”的时候我盯着题目愣了好几秒——给一棵树让你找出所有能让整棵树高度最小的根节点。说实话树的高度这个概念本身不难但“找根”这件事放在图论里就有点绕了。最要命的是如果你上来就枚举每个节点当根去算高度大概率会写出一份能跑但会超时的代码。这道题在面试中出现的频率不算低尤其是偏向图论、拓扑排序、BFS 的岗位。它考察的不是你会不会递归求深度而是你能不能从一个看似是“搜索”的问题里看出“剥叶子”的本质。这篇文章我就从题目理解、暴力思路、最优解法、数学直觉到代码落地完整拆一遍这道题保证你看完能自己写出来而且知道为什么这么写。1. 题目到底在问什么先把“最小高度树”这层窗户纸捅破1.1 从一个反直觉的问题开始题目输入是一个n个节点的无向树节点编号从0到n-1给一个边数组edges。你需要找出所有的根节点使得以该节点为根时整棵树的高度最小返回这些根节点的编号列表。第一眼看上去这题像是一个“搜索最优根”的问题甚至有点像“找树的重心”。但实际上它和重心压根不是一回事。树的重心是删掉这个节点后剩下的子树中最大的那棵尽量小最小高度树则是要让“从根到最远叶子”的距离最短。两者有时候重合但绝大多数情况不是一个节点。核心概念只有两个树的高度和根节点的选择。树的高度在以某个节点为根时定义为从根到任意叶子节点的最大边数。注意是边数不是节点数。比如只有一个节点的树高度是 0不是 1。这个细节在写代码和推算复杂度的时候经常被忽略。1.2 为什么这个问题值得认真做很多刷题的人看到“无向树”就直接开始写深度优先搜索DFS枚举所有节点作为根然后每次递归算高度。这种写法在n很小的时候完全没有问题但一旦n到了 10^4、10^5 的量级就会立刻暴露性能问题。题目虽然没有明确给出n的极限但按照 LeetCode 的惯例这类题的数据规模通常不会让你用 O(n^2) 的解法轻易跑过去。更重要的是这道题隐藏着一个非常漂亮的数学结论一棵树的最小高度根最多只有两个。当你把证据递到面试官面前的时候很多人才会意识到这不是一道“暴力搜索题”而是一道需要动脑子找规律的题。所以这道题的价值在于它逼你从“算法模板”切换到“图论直觉”。理解了它你以后再遇到类似的“在树上找一个特殊节点”的题目会多一层解决问题的思路。2. 暴力枚举为什么可行但不可取一个朴素的起点2.1 最直接的方案每个节点都试一遍剥开所有技巧不谈最简单的做法如下对每个节点i把i当成根做一次 DFS 或 BFS算出以i为根时树的最大深度也就是高度。然后遍历所有节点找到最小高度对应的所有根节点。def findMinHeightTrees(n, edges): if n 1: return [0] from collections import defaultdict, deque graph defaultdict(list) for u, v in edges: graph[u].append(v) graph[v].append(u) def bfs_height(root): visited [False] * n visited[root] True q deque([(root, 0)]) max_depth 0 while q: node, depth q.popleft() max_depth max(max_depth, depth) for nei in graph[node]: if not visited[nei]: visited[nei] True q.append((nei, depth 1)) return max_depth heights [bfs_height(i) for i in range(n)] min_h min(heights) return [i for i, h in enumerate(heights) if h min_h]这段代码逻辑上完全正确轻轻松松就能通过示例。但它的缺点是明显的对于每个节点都要遍历整张图一次整体复杂度是 O(n * (n e))。由于题目给的是树e n - 1所以复杂度是 O(n^2)。2.2 复杂度的账要算清楚假设n 10^4O(n^2) 意味着大约 10^8 次操作这基本逼近单次运行的性能上限大部分评测环境 1 秒能跑 10^7 到 10^8 次简单操作。当n 10^5时10^10 次操作无论如何都跑不动了。所以暴力方法只适合用来验证最优解法的正确性不适合作为最终提交的答案。另外还有个小坑如果你用递归 DFS 去求高度在极端情况下比如树退化成一个长链会爆栈。LeetCode 的 Python 环境虽然默认改了递归深度但你这个递归深度是跟着树的深度走的长链深度可能达到 10^4 甚至更高自己本地跑很容易RecursionError。所以暴力写法里 BFS 比 DFS 更稳妥。但暴力解法的最大价值在于它让我们看到了问题的一个关键观察——高度由“树中最远的一对叶子之间的距离”决定这个距离就是树的直径。整棵树的高度本质上被直径的长度支配。沿着这个方向想就能找到更聪明的办法。3. 核心思路从叶子向里“剥洋葱”3.1 一个反直觉的观察叶子节点能当根吗先想一个问题叶子节点有没有可能成为最小高度树的根我们随便举一个例子。一棵三个节点的链0 - 1 - 2如果以0为根树的高度是 2以1为根高度是 1。很明显叶子节点不是最优根。那是不是所有情况下叶子节点都不可能是最优根答案基本是当树的节点数大于 2 时叶子节点一定不是最优根。证明过程也很直观假设u是一个叶子节点v是它唯一的邻居。如果以u为根那么v的深度是 1其他所有节点都挂在v下面。如果换一个思路以v为根那么u的深度变成 1但v下面所有其他节点的深度都减 1。只要v下面除了u以外还有一个节点树的总高度就会变小或至少不会变大。所以叶子节点永远可以“把根让给邻居”并且不会让结果变差。这个观察直接指向了一个策略叶子节点不可能是答案那就把它们从树里去掉。去掉之后新的叶子节点又出现了再继续去掉。这就是“剥洋葱”的思路。剥到最后剩下的一个或两个节点就是我们要找的最小高度根。3.2 为什么“剥叶子”能保证答案正确如果把所有当前叶子节点一次性去掉那么树的直径会缩短大约 2去掉叶子层后原来端点之间的距离从两端各减 1。树的直径每次少 2最终当直径变成 0 或 1 的时候剩下的节点就位于树的“中心”。这个中心就是最小高度树的根。高度最小本质上就是让根节点尽量靠近所有节点的“中间位置”。一棵树的中心最多有两个直径长度为偶数时有一个中心奇数时有相邻的两个中心所以最终答案最多两个节点。剥叶子的过程就像逐步把无效的边缘节点删掉剩下的节点自然是中心区域。这个思路的数学基础是树的“中心”概念树的中心定义为到所有节点最大距离最小的节点集合。树中心要么是一个点要么是两个相邻的点。以任意中心为根树的高度都是半径ceil(直径 / 2)这是全局最小高度。所以绕了一圈这道题的本质变成如何高效地找到一棵无向树的中心。剥叶子法是最直观的实现方式。4. 为什么答案最多只有两个根一个值得深挖的数学事实4.1 直径、中心和删叶子的关系很多博客会直接告诉你“答案最多两个”但没有解释为什么。我们稍微展开一点。一棵树里任意两点之间只有一条简单路径。树中最长的那条简单路径的两个端点就是直径的端点。假设直径长度为D边的数量。不管以哪个节点为根直径的两个端点到根的距离之和至少是D所以树的高度至少是ceil(D / 2)。什么时候能达到这个下界当且仅当根正好在直径的“中点”上。如果D是偶数中点是一个节点这是唯一的中心对应唯一的最小高度根如果D是奇数中点是一条边的中间位置那么这条边的两个端点都是中心对应两个最小高度根。每剥掉一层当前叶子节点所有叶子到中心的距离就减 1但那个“最低下界”ceil(D / 2)也跟着减 1。持续剥下去当剥到直径变成 0 或 1 的时候剩下的节点自然就是中心。这个结论的价值不只是让你写出答案更重要的是你在解释思路的时候能说清楚为什么循环条件是n 2而不是n 0。因为当剩下 2 个节点时这 2 个节点相邻直径是 1它们俩都是中心剩下 1 个节点时它自己就是中心。如果继续往下剥就连中心也剥没了。4.2 两个根的情况链状树的直觉最容易理解“两个根”的例子是一条长链比如0 - 1 - 2 - 3 - 4一共有 5 个节点直径是 4。中心是中点2所以答案只有一个节点[2]。但是如果是0 - 1 - 2 - 3 - 4 - 56 个节点直径是 5中心落在2和3之间的边上此时答案就是[2, 3]。试着用剥叶子法推一遍先去掉叶子0和5剩下1 - 2 - 3 - 4再去掉新的叶子1和4剩下2 - 3。这时节点数等于 2停止。剩下两个节点就是答案。这个例子能帮你直观建立“答案最多两个”的信赖感因为一条链剥一次两端各少一个最后要么剩一个奇数长度要么剩两个偶数长度。对于任意形状的树虽然结构复杂但剥叶子的最终形态同样只有这两种。下表总结了节点数与答案个数的对应关系树的直径 D中心数量最小高度答案节点个数偶数1D / 21奇数2(D 1) / 220单节点1015. 代码落地与边界情况从思路到 AC5.1 Python 实现分层剥叶法from collections import defaultdict, deque def findMinHeightTrees(n, edges): if n 1: return [0] graph defaultdict(list) degree [0] * n for u, v in edges: graph[u].append(v) graph[v].append(u) degree[u] 1 degree[v] 1 leaves deque([i for i in range(n) if degree[i] 1]) remaining n while remaining 2: leaf_count len(leaves) remaining - leaf_count for _ in range(leaf_count): leaf leaves.popleft() for neighbor in graph[leaf]: degree[neighbor] - 1 if degree[neighbor] 1: leaves.append(neighbor) return list(leaves)这段代码有几个关键点值得强调第一leaf_count必须在一轮开始时固定下来这就是“分层”的思想。如果不分层直接用while leaves:每弹一个叶子就处理一个会出现同一个“轮次”里新出现的叶子也被立刻剥掉的问题。极端情况下会把整棵树剥光最后返回空数组。第二remaining变量统计的是还没有被剥掉的节点数量。当它小于等于 2 时循环停止。此时leaves队列里保存的就是剩余的节点可能是 1 个或 2 个。注意当remaining变成 2 的时候两个节点的度数可能都是 1但这没关系它们就是答案。第三因为是树所以不需要visited数组。每个节点只会被它的邻居处理到一次从叶子向内收敛不会走回头路。这比通用图 BFS 要简单得多。5.2 Java 实现同样的逻辑不同的写法class Solution { public ListInteger findMinHeightTrees(int n, int[][] edges) { if (n 1) { return Collections.singletonList(0); } ListSetInteger graph new ArrayList(); for (int i 0; i n; i) { graph.add(new HashSet()); } int[] degree new int[n]; for (int[] edge : edges) { int u edge[0]; int v edge[1]; graph.get(u).add(v); graph.get(v).add(u); degree[u]; degree[v]; } QueueInteger leaves new LinkedList(); for (int i 0; i n; i) { if (degree[i] 1) { leaves.offer(i); } } int remaining n; while (remaining 2) { int size leaves.size(); remaining - size; for (int i 0; i size; i) { int leaf leaves.poll(); for (int neighbor : graph.get(leaf)) { if (graph.get(neighbor).contains(leaf)) { graph.get(neighbor).remove(leaf); } degree[neighbor]--; if (degree[neighbor] 1) { leaves.offer(neighbor); } } graph.get(leaf).clear(); } } return new ArrayList(leaves); } }Java 版本里我用SetInteger作为邻接表主要是为了演示如何在遍历时安全地删除边。实际上直接用ListInteger也没问题只需要在剥叶子时记录一下邻居最后不用真的删边——因为每个叶子只会被处理一次后面不会再访问它。但用Set代码语义更清晰。需要注意的一个小坑是 Java 的LinkedList是不允许在遍历的同时修改的所以这里用for (int i 0; i size; i)按次数取出队列元素而不是用增强 for 遍历队列。5.3 边界条件与常见坑n 1时没有边没有任何节点度数为 1如果直接执行剥叶逻辑remaining始终是 1但leaves为空最后会返回空列表。所以必须特判。n 2时两个节点度数都是 1循环条件remaining 2不成立直接返回[0, 1]。这刚好是正确答案因为两个节点互为叶子时两个节点都适合当根。输入的边数组可能顺序不同但无向图建图时不要漏掉双向边。队列弹出的顺序不重要因为每一轮处理的是当前所有叶子不关心谁先谁后。时间复杂度和空间复杂度都是 O(n)。建图需要 O(n) 空间队列最多容纳 O(n) 个节点。实际提交时最容易翻车的其实不是算法本身反而是对“叶子”的定义。在树里叶子节点的度数是 1但如果n 1唯一节点的度数是 0它既是根也是叶子。如果不特判边界用例直接挂掉。我在第一次写这道题的时候就是在n 1上栽的后来养成了一个习惯凡是树相关的题先问自己n 1和n 2的情况怎么处理。6. 算法延伸剥叶法还能用在哪些地方6.1 与“求树直径”问题的对照求解最小高度树还有一种思路先求树的直径然后找直径的中点。求树直径的标准方法是两次 BFS/DFS从任意节点出发找到最远的节点 A再从 A 出发找到最远的节点 B。A 和 B 就是直径的两个端点。找到直径之后沿着直径路径找中点就能得到答案。这个方法的最大好处是思路直白但实现起来比剥叶子要麻烦一些你需要构建父节点数组然后从 B 回溯路径。剥叶子法则不需要记录路径代码上省事很多。两者时间复杂度都是 O(n)但面试时剥叶子法的推导过程更自然也更难被面试官追问卡住。有趣的是如果你理解了这两种解法你会发现它们本质上是同一个定理的两面树的中心与最小高度根一一对应。剥叶子是直接从中心定义出发求解而两次 BFS 是先找直径再定位中心。6.2 在分布式系统和网络设计里的现实意义“最小高度树”不完全是一道纯刷题用的题目。在分布式系统里如果有一堆节点需要以广播或汇聚的方式通信选择一个恰当的中心节点可以显著减少消息传播的最大跳数。具体到实际场景P2P 网络中的超级节点选择让超级节点尽量处在网络的中心位置能降低平均延迟避免边缘节点承担过多的转发压力。数据库集群中的主节点选举在分布式数据库里主节点和副本之间需要同步日志。如果主节点太偏某些副本的同步延迟会很糟糕。用最小高度树的思路选主能优化最坏情况下的同步延迟。消息队列的 broker 部署如果你的系统里有一组消息代理需要互相转发消息把转发节点放在拓扑中心可以减少消息在网络里经过的跳数端到端延迟自然就降下来了。当然真实系统里会有带宽、容灾、地理位置等更多约束不会真的只靠一个算法定方案但“找中心”这个思路本身是非常通用的。还有一个比较有意思的延伸剥叶子法的思想还可以用来解决“找到所有距离某个节点不超过 k 的节点”这类问题或者变种题比如“最小高度森林”多个连通分量。只要你理解了拓扑排序式的层级剥离这些题目都是同一个套路。最后分享一个我自己的刷题习惯遇到这种“在树上找特殊节点”的题先别急着写代码先在草稿纸上画一个长链的树和一个星形的树手动演算一遍候选节点可能的位置。画的次数多了你就会形成一种直觉——凡是要求“全局最平衡”的树上问题答案大概率藏在树的中心或者重心附近。有了这个直觉再去看题解就不会觉得算法是天外飞仙了。 LeetCode 310 最小高度树：用剥叶子法找到树的中心
第一次在LeetCode上刷到第310题“最小高度树”的时候我盯着题目愣了好几秒——给一棵树让你找出所有能让整棵树高度最小的根节点。说实话树的高度这个概念本身不难但“找根”这件事放在图论里就有点绕了。最要命的是如果你上来就枚举每个节点当根去算高度大概率会写出一份能跑但会超时的代码。这道题在面试中出现的频率不算低尤其是偏向图论、拓扑排序、BFS 的岗位。它考察的不是你会不会递归求深度而是你能不能从一个看似是“搜索”的问题里看出“剥叶子”的本质。这篇文章我就从题目理解、暴力思路、最优解法、数学直觉到代码落地完整拆一遍这道题保证你看完能自己写出来而且知道为什么这么写。1. 题目到底在问什么先把“最小高度树”这层窗户纸捅破1.1 从一个反直觉的问题开始题目输入是一个n个节点的无向树节点编号从0到n-1给一个边数组edges。你需要找出所有的根节点使得以该节点为根时整棵树的高度最小返回这些根节点的编号列表。第一眼看上去这题像是一个“搜索最优根”的问题甚至有点像“找树的重心”。但实际上它和重心压根不是一回事。树的重心是删掉这个节点后剩下的子树中最大的那棵尽量小最小高度树则是要让“从根到最远叶子”的距离最短。两者有时候重合但绝大多数情况不是一个节点。核心概念只有两个树的高度和根节点的选择。树的高度在以某个节点为根时定义为从根到任意叶子节点的最大边数。注意是边数不是节点数。比如只有一个节点的树高度是 0不是 1。这个细节在写代码和推算复杂度的时候经常被忽略。1.2 为什么这个问题值得认真做很多刷题的人看到“无向树”就直接开始写深度优先搜索DFS枚举所有节点作为根然后每次递归算高度。这种写法在n很小的时候完全没有问题但一旦n到了 10^4、10^5 的量级就会立刻暴露性能问题。题目虽然没有明确给出n的极限但按照 LeetCode 的惯例这类题的数据规模通常不会让你用 O(n^2) 的解法轻易跑过去。更重要的是这道题隐藏着一个非常漂亮的数学结论一棵树的最小高度根最多只有两个。当你把证据递到面试官面前的时候很多人才会意识到这不是一道“暴力搜索题”而是一道需要动脑子找规律的题。所以这道题的价值在于它逼你从“算法模板”切换到“图论直觉”。理解了它你以后再遇到类似的“在树上找一个特殊节点”的题目会多一层解决问题的思路。2. 暴力枚举为什么可行但不可取一个朴素的起点2.1 最直接的方案每个节点都试一遍剥开所有技巧不谈最简单的做法如下对每个节点i把i当成根做一次 DFS 或 BFS算出以i为根时树的最大深度也就是高度。然后遍历所有节点找到最小高度对应的所有根节点。def findMinHeightTrees(n, edges): if n 1: return [0] from collections import defaultdict, deque graph defaultdict(list) for u, v in edges: graph[u].append(v) graph[v].append(u) def bfs_height(root): visited [False] * n visited[root] True q deque([(root, 0)]) max_depth 0 while q: node, depth q.popleft() max_depth max(max_depth, depth) for nei in graph[node]: if not visited[nei]: visited[nei] True q.append((nei, depth 1)) return max_depth heights [bfs_height(i) for i in range(n)] min_h min(heights) return [i for i, h in enumerate(heights) if h min_h]这段代码逻辑上完全正确轻轻松松就能通过示例。但它的缺点是明显的对于每个节点都要遍历整张图一次整体复杂度是 O(n * (n e))。由于题目给的是树e n - 1所以复杂度是 O(n^2)。2.2 复杂度的账要算清楚假设n 10^4O(n^2) 意味着大约 10^8 次操作这基本逼近单次运行的性能上限大部分评测环境 1 秒能跑 10^7 到 10^8 次简单操作。当n 10^5时10^10 次操作无论如何都跑不动了。所以暴力方法只适合用来验证最优解法的正确性不适合作为最终提交的答案。另外还有个小坑如果你用递归 DFS 去求高度在极端情况下比如树退化成一个长链会爆栈。LeetCode 的 Python 环境虽然默认改了递归深度但你这个递归深度是跟着树的深度走的长链深度可能达到 10^4 甚至更高自己本地跑很容易RecursionError。所以暴力写法里 BFS 比 DFS 更稳妥。但暴力解法的最大价值在于它让我们看到了问题的一个关键观察——高度由“树中最远的一对叶子之间的距离”决定这个距离就是树的直径。整棵树的高度本质上被直径的长度支配。沿着这个方向想就能找到更聪明的办法。3. 核心思路从叶子向里“剥洋葱”3.1 一个反直觉的观察叶子节点能当根吗先想一个问题叶子节点有没有可能成为最小高度树的根我们随便举一个例子。一棵三个节点的链0 - 1 - 2如果以0为根树的高度是 2以1为根高度是 1。很明显叶子节点不是最优根。那是不是所有情况下叶子节点都不可能是最优根答案基本是当树的节点数大于 2 时叶子节点一定不是最优根。证明过程也很直观假设u是一个叶子节点v是它唯一的邻居。如果以u为根那么v的深度是 1其他所有节点都挂在v下面。如果换一个思路以v为根那么u的深度变成 1但v下面所有其他节点的深度都减 1。只要v下面除了u以外还有一个节点树的总高度就会变小或至少不会变大。所以叶子节点永远可以“把根让给邻居”并且不会让结果变差。这个观察直接指向了一个策略叶子节点不可能是答案那就把它们从树里去掉。去掉之后新的叶子节点又出现了再继续去掉。这就是“剥洋葱”的思路。剥到最后剩下的一个或两个节点就是我们要找的最小高度根。3.2 为什么“剥叶子”能保证答案正确如果把所有当前叶子节点一次性去掉那么树的直径会缩短大约 2去掉叶子层后原来端点之间的距离从两端各减 1。树的直径每次少 2最终当直径变成 0 或 1 的时候剩下的节点就位于树的“中心”。这个中心就是最小高度树的根。高度最小本质上就是让根节点尽量靠近所有节点的“中间位置”。一棵树的中心最多有两个直径长度为偶数时有一个中心奇数时有相邻的两个中心所以最终答案最多两个节点。剥叶子的过程就像逐步把无效的边缘节点删掉剩下的节点自然是中心区域。这个思路的数学基础是树的“中心”概念树的中心定义为到所有节点最大距离最小的节点集合。树中心要么是一个点要么是两个相邻的点。以任意中心为根树的高度都是半径ceil(直径 / 2)这是全局最小高度。所以绕了一圈这道题的本质变成如何高效地找到一棵无向树的中心。剥叶子法是最直观的实现方式。4. 为什么答案最多只有两个根一个值得深挖的数学事实4.1 直径、中心和删叶子的关系很多博客会直接告诉你“答案最多两个”但没有解释为什么。我们稍微展开一点。一棵树里任意两点之间只有一条简单路径。树中最长的那条简单路径的两个端点就是直径的端点。假设直径长度为D边的数量。不管以哪个节点为根直径的两个端点到根的距离之和至少是D所以树的高度至少是ceil(D / 2)。什么时候能达到这个下界当且仅当根正好在直径的“中点”上。如果D是偶数中点是一个节点这是唯一的中心对应唯一的最小高度根如果D是奇数中点是一条边的中间位置那么这条边的两个端点都是中心对应两个最小高度根。每剥掉一层当前叶子节点所有叶子到中心的距离就减 1但那个“最低下界”ceil(D / 2)也跟着减 1。持续剥下去当剥到直径变成 0 或 1 的时候剩下的节点自然就是中心。这个结论的价值不只是让你写出答案更重要的是你在解释思路的时候能说清楚为什么循环条件是n 2而不是n 0。因为当剩下 2 个节点时这 2 个节点相邻直径是 1它们俩都是中心剩下 1 个节点时它自己就是中心。如果继续往下剥就连中心也剥没了。4.2 两个根的情况链状树的直觉最容易理解“两个根”的例子是一条长链比如0 - 1 - 2 - 3 - 4一共有 5 个节点直径是 4。中心是中点2所以答案只有一个节点[2]。但是如果是0 - 1 - 2 - 3 - 4 - 56 个节点直径是 5中心落在2和3之间的边上此时答案就是[2, 3]。试着用剥叶子法推一遍先去掉叶子0和5剩下1 - 2 - 3 - 4再去掉新的叶子1和4剩下2 - 3。这时节点数等于 2停止。剩下两个节点就是答案。这个例子能帮你直观建立“答案最多两个”的信赖感因为一条链剥一次两端各少一个最后要么剩一个奇数长度要么剩两个偶数长度。对于任意形状的树虽然结构复杂但剥叶子的最终形态同样只有这两种。下表总结了节点数与答案个数的对应关系树的直径 D中心数量最小高度答案节点个数偶数1D / 21奇数2(D 1) / 220单节点1015. 代码落地与边界情况从思路到 AC5.1 Python 实现分层剥叶法from collections import defaultdict, deque def findMinHeightTrees(n, edges): if n 1: return [0] graph defaultdict(list) degree [0] * n for u, v in edges: graph[u].append(v) graph[v].append(u) degree[u] 1 degree[v] 1 leaves deque([i for i in range(n) if degree[i] 1]) remaining n while remaining 2: leaf_count len(leaves) remaining - leaf_count for _ in range(leaf_count): leaf leaves.popleft() for neighbor in graph[leaf]: degree[neighbor] - 1 if degree[neighbor] 1: leaves.append(neighbor) return list(leaves)这段代码有几个关键点值得强调第一leaf_count必须在一轮开始时固定下来这就是“分层”的思想。如果不分层直接用while leaves:每弹一个叶子就处理一个会出现同一个“轮次”里新出现的叶子也被立刻剥掉的问题。极端情况下会把整棵树剥光最后返回空数组。第二remaining变量统计的是还没有被剥掉的节点数量。当它小于等于 2 时循环停止。此时leaves队列里保存的就是剩余的节点可能是 1 个或 2 个。注意当remaining变成 2 的时候两个节点的度数可能都是 1但这没关系它们就是答案。第三因为是树所以不需要visited数组。每个节点只会被它的邻居处理到一次从叶子向内收敛不会走回头路。这比通用图 BFS 要简单得多。5.2 Java 实现同样的逻辑不同的写法class Solution { public ListInteger findMinHeightTrees(int n, int[][] edges) { if (n 1) { return Collections.singletonList(0); } ListSetInteger graph new ArrayList(); for (int i 0; i n; i) { graph.add(new HashSet()); } int[] degree new int[n]; for (int[] edge : edges) { int u edge[0]; int v edge[1]; graph.get(u).add(v); graph.get(v).add(u); degree[u]; degree[v]; } QueueInteger leaves new LinkedList(); for (int i 0; i n; i) { if (degree[i] 1) { leaves.offer(i); } } int remaining n; while (remaining 2) { int size leaves.size(); remaining - size; for (int i 0; i size; i) { int leaf leaves.poll(); for (int neighbor : graph.get(leaf)) { if (graph.get(neighbor).contains(leaf)) { graph.get(neighbor).remove(leaf); } degree[neighbor]--; if (degree[neighbor] 1) { leaves.offer(neighbor); } } graph.get(leaf).clear(); } } return new ArrayList(leaves); } }Java 版本里我用SetInteger作为邻接表主要是为了演示如何在遍历时安全地删除边。实际上直接用ListInteger也没问题只需要在剥叶子时记录一下邻居最后不用真的删边——因为每个叶子只会被处理一次后面不会再访问它。但用Set代码语义更清晰。需要注意的一个小坑是 Java 的LinkedList是不允许在遍历的同时修改的所以这里用for (int i 0; i size; i)按次数取出队列元素而不是用增强 for 遍历队列。5.3 边界条件与常见坑n 1时没有边没有任何节点度数为 1如果直接执行剥叶逻辑remaining始终是 1但leaves为空最后会返回空列表。所以必须特判。n 2时两个节点度数都是 1循环条件remaining 2不成立直接返回[0, 1]。这刚好是正确答案因为两个节点互为叶子时两个节点都适合当根。输入的边数组可能顺序不同但无向图建图时不要漏掉双向边。队列弹出的顺序不重要因为每一轮处理的是当前所有叶子不关心谁先谁后。时间复杂度和空间复杂度都是 O(n)。建图需要 O(n) 空间队列最多容纳 O(n) 个节点。实际提交时最容易翻车的其实不是算法本身反而是对“叶子”的定义。在树里叶子节点的度数是 1但如果n 1唯一节点的度数是 0它既是根也是叶子。如果不特判边界用例直接挂掉。我在第一次写这道题的时候就是在n 1上栽的后来养成了一个习惯凡是树相关的题先问自己n 1和n 2的情况怎么处理。6. 算法延伸剥叶法还能用在哪些地方6.1 与“求树直径”问题的对照求解最小高度树还有一种思路先求树的直径然后找直径的中点。求树直径的标准方法是两次 BFS/DFS从任意节点出发找到最远的节点 A再从 A 出发找到最远的节点 B。A 和 B 就是直径的两个端点。找到直径之后沿着直径路径找中点就能得到答案。这个方法的最大好处是思路直白但实现起来比剥叶子要麻烦一些你需要构建父节点数组然后从 B 回溯路径。剥叶子法则不需要记录路径代码上省事很多。两者时间复杂度都是 O(n)但面试时剥叶子法的推导过程更自然也更难被面试官追问卡住。有趣的是如果你理解了这两种解法你会发现它们本质上是同一个定理的两面树的中心与最小高度根一一对应。剥叶子是直接从中心定义出发求解而两次 BFS 是先找直径再定位中心。6.2 在分布式系统和网络设计里的现实意义“最小高度树”不完全是一道纯刷题用的题目。在分布式系统里如果有一堆节点需要以广播或汇聚的方式通信选择一个恰当的中心节点可以显著减少消息传播的最大跳数。具体到实际场景P2P 网络中的超级节点选择让超级节点尽量处在网络的中心位置能降低平均延迟避免边缘节点承担过多的转发压力。数据库集群中的主节点选举在分布式数据库里主节点和副本之间需要同步日志。如果主节点太偏某些副本的同步延迟会很糟糕。用最小高度树的思路选主能优化最坏情况下的同步延迟。消息队列的 broker 部署如果你的系统里有一组消息代理需要互相转发消息把转发节点放在拓扑中心可以减少消息在网络里经过的跳数端到端延迟自然就降下来了。当然真实系统里会有带宽、容灾、地理位置等更多约束不会真的只靠一个算法定方案但“找中心”这个思路本身是非常通用的。还有一个比较有意思的延伸剥叶子法的思想还可以用来解决“找到所有距离某个节点不超过 k 的节点”这类问题或者变种题比如“最小高度森林”多个连通分量。只要你理解了拓扑排序式的层级剥离这些题目都是同一个套路。最后分享一个我自己的刷题习惯遇到这种“在树上找特殊节点”的题先别急着写代码先在草稿纸上画一个长链的树和一个星形的树手动演算一遍候选节点可能的位置。画的次数多了你就会形成一种直觉——凡是要求“全局最平衡”的树上问题答案大概率藏在树的中心或者重心附近。有了这个直觉再去看题解就不会觉得算法是天外飞仙了。