题目描述
思路解析动画文字版
笨办法：每个点都试一遍：暴力是拿每个点当根各量一次高度。能算对，但 n 一大就慢成 O(n²)。我们想要一个一遍就找到答案的办法。
换个角度：找「最中间」的点：把树想成一根有分叉的绳子：越靠边的点当根越「拎得长」，越中间越「扁」。所以答案就是树的中心点，而中心最多 2 个。
优解：一层层「剥叶子」：像剥洋葱：每轮把最外圈的叶子一次性全删掉，里面一圈就露出来变成新叶子，接着剥。剥到只剩 1～2 个点停手，它们就是最中间的根。下面一帧删一圈地演给你看。
例一 · 建图 + 数度数：先把例一画出来：点 3 连着 0、1、2、4，点 4 又连着 5。每个点头顶标的是它的度数（连了几条边）。蓝色 = 当前还活着的点。
找出第一圈叶子：扫一遍度数，把度数等于 1 的点挑出来——就是 0、1、2、5（橙色高亮）。它们是树最外圈的叶子，这一轮要被一起剥掉。
锁定中心候选 · 3 和 4 度数最高：对照着看：橙圈是要剥的叶子，紫圈 3、4 度数最高、藏在最里圈。剥的过程其实就是外圈不断把里圈「逼」出来——盯着 3、4 的度数怎么往下掉。
剥叶子 0 · 邻居 3 度数减一：先剥 0（变绿 = 已删，连它的边一起消失）。它唯一的邻居 3 失去一条边，度数从 4 降到 3。0 从本轮叶子名单里划掉。
剥叶子 1 · 邻居 3 度数再减一：再剥 1（变绿）。邻居还是 3，它的度数从 3 降到 2。注意：3 暂时没降到 1，所以它这一轮还不算新叶子，先不入名单。
剥叶子 2 · 邻居 3 度数减到 1：剥 2（变绿）。3 的度数降到 1 了！它现在变成了新叶子。但它是下一轮才剥的——本轮的名单在开始时就定死了，新叶子排进下一轮。
剥叶子 5 · 邻居 4 度数减一：剥本轮最后一个 5（变绿）。它的邻居 4 度数从 2 降到 1，4 也成了新叶子。第一圈 0、1、2、5 全剥完，名单清空。
第一圈剥完 · 看剩几个点：剥完一圈，外圈四个点都没了（灰绿），只剩 3 和 4 中间还连着一条边。剩下点数 = 2，已经到了停手线。
停手判定 · 剩点 ≤ 2：判一下：剩下的点 ≤ 2 就不再剥了。现在剩 3 和 4 两个点（橙色高亮 = 命中中心），它们就是树的中心，循环到此结束。
例一收工 · 中心 = {3,4}：剥到只剩 3、4，它们就是让树最矮的根。下方「已完成」是删点顺序：先剥外圈 0、1、2、5，最后停在中心 3、4 → 答案 [3,4]。
例二 · 星形树建图：再看例二 n=4：点 1 在正中央，连着 0、2、3。1 的度数是 3，其余三个点度数都是 1。猜也猜得到中心是 1，剥一圈验证给你看。
例二 · 选出本轮叶子 {0,2,3}：把度为 1 的 0、2、3 全选进本轮名单（橙色）。它们都挂在中心 1 上，这一轮要一起剥掉。
例二 · 剥 0 · deg[1]: 3→2：剥 0（变绿）。中心 1 掉一条边，度数 3→2，还没到 1，所以 1 这一轮不会成为新叶子。继续剥名单里的 2、3。
例二 · 剥 2 · deg[1]: 2→1：剥 2（变绿）。1 的度数降到 1，理论上成了新叶子；但本轮名单开始时就定死，1 只会排进下一轮。本轮还剩 3 要剥。
例二 · 剥 3 · deg[1]: 1→0：剥掉本轮最后一个 3（变绿），中心 1 失去全部边、彻底孤立。本轮 0、2、3 全剥完，剩下点数 = 1 ≤ 2，停手。
例二收工 · 中心 = {1}：只剩 1 一个点，它就是唯一中心 → 答案 [1]。这说明中心可能 1 个也可能 2 个，取决于直径中点落在一个点上还是一条边两端，不看总点数奇偶。
例三 · 一条链 0-1-2-3：再看一条链 0-1-2-3。两端 0、3 度数为 1 是叶子，中间 1、2 度数为 2。这是会剥出两个中心的经典例子，剥给你看。
链 · 第一圈叶子 = {0,3}：把度为 1 的 0、3 两头 一起选进本轮名单（橙色）。注意是同一轮两个一起剥——这正是「逐个剥会出错」的关键所在。
链 · 剥掉两头 0、3：两头 0、3 同时剥掉（变绿）。1 和 2 各掉一条边，度数都降到 1，中间只剩 1—2 一条边。剩点 = 2，到停手线。
链收工 · 中心 = {1,2}：剩 1、2 两个点 → 答案 [1,2]。试想若一个个剥：先剥 0 再剥 3，1 会先变叶子被误删，最后只剩 2——答案就错了。所以必须整圈一起剥。
为什么最多 2 个中心：记住这个结论：答案最多 2 个。原理就是树的中心是「最长路径的中点」，中点最多占两个相邻的点。
套路模板：凡是「由外向内层层剥、找中心」的树/图题，都能套这个度数 + 队列的剥叶模板。
边界三连：记住两个特判：n≤2 时所有点都是答案。链状树剥两头后，会停在最中间的 1～2 个点。
面试追问：面试常追问 为什么最多 2 个 和 两次 DFS 求直径中点 的等价解法，都能从「中心 = 直径中点」推出来。
参考代码
from collections import dequeclass Solution: def findMinHeightTrees(self, n, edges): if n <= 2: return list(range(n)) # 0~1 个点直接是答案 g = [[] for _ in range(n)] deg = [0] * n for a, b in edges: # 建邻接表 + 数度数 g[a].append(b); g[b].append(a) deg[a] += 1; deg[b] += 1 leaves = deque(i for i in range(n) if deg[i] == 1) remaining = n while remaining > 2: # 剥到剩 ≤2 停手 sz = len(leaves) remaining -= sz # 整圈一起删 for _ in range(sz): u = leaves.popleft() for v in g[u]: deg[v] -= 1 # 邻居度数减一 if deg[v] == 1: # 变新叶子 → 下轮剥 leaves.append(v) return list(leaves) # 剩下的就是中心复杂度
- 时间：O(n)，树有 n-1 条边，每个点入队出队一次、每条边扫两次
- 空间：O(n)，邻接表 + 度数数组 + 叶子队列
易错点
面试追问把动画讲成自己的话
追问为什么答案最多 2 个？
追问能不能用两次 DFS 找直径再取中点？
追问剥叶法和拓扑排序什么关系？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
无向图中连通分量的数目
LeetCode 323 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题