最小高度树 图解题解

这道题到底在问什么

输入

n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]

输出

[3,4]

输入

n = 4, edges = [[1,0],[1,2],[1,3]]

输出

[1]

先想最直接的笨办法

暴力是拿每个点当根各量一次高度。能算对，但 n 一大就慢成 O(n²)。我们想要一个一遍就找到答案的办法。（动画第 3 步）

最优解：一步一步想明白

1. 3n 次遍历，太慢暴力是拿每个点当根各量一次高度。能算对，但 n 一大就慢成 O(n²)。我们想要一个一遍就找到答案的办法。
2. 4中心 = 离最远点最近把树想成一根有分叉的绳子：越靠边的点当根越「拎得长」，越中间越「扁」。所以答案就是树的中心点，而中心最多 2 个。
3. 5拓扑剥叶 · 由外向内像剥洋葱：每轮把最外圈的叶子一次性全删掉，里面一圈就露出来变成新叶子，接着剥。剥到只剩 1～2 个点停手，它们就是最中间的根。下面一帧删一圈地演给你看。
4. 6n=6 · 全部存活先把例一画出来：点 3 连着 0、1、2、4，点 4 又连着 5。每个点头顶标的是它的度数（连了几条边）。蓝色 = 当前还活着的点。
5. 7度为 1 的点 = {0,1,2,5}扫一遍度数，把度数等于 1 的点挑出来——就是 0、1、2、5（橙色高亮）。它们是树最外圈的叶子，这一轮要被一起剥掉。
6. 8deg[3]=4, deg[4]=2 居内圈对照着看：橙圈是要剥的叶子，紫圈 3、4 度数最高、藏在最里圈。剥的过程其实就是外圈不断把里圈「逼」出来——盯着 3、4 的度数怎么往下掉。
7. 9删 0 → deg[3]: 4→3先剥 0（变绿 = 已删，连它的边一起消失）。它唯一的邻居 3 失去一条边，度数从 4 降到 3。0 从本轮叶子名单里划掉。
8. 10删 1 → deg[3]: 3→2再剥 1（变绿）。邻居还是 3，它的度数从 3 降到 2。注意：3 暂时没降到 1，所以它这一轮还不算新叶子，先不入名单。
9. 11删 2 → deg[3]: 2→1剥 2（变绿）。3 的度数降到 1 了！它现在变成了新叶子。但它是下一轮才剥的——本轮的名单在开始时就定死了，新叶子排进下一轮。
10. 12删 5 → deg[4]: 2→1剥本轮最后一个 5（变绿）。它的邻居 4 度数从 2 降到 1，4 也成了新叶子。第一圈 0、1、2、5 全剥完，名单清空。
11. 13剩 {3,4}，还各连着一条边剥完一圈，外圈四个点都没了（灰绿），只剩 3 和 4 中间还连着一条边。剩下点数 = 2，已经到了停手线。
12. 14remaining=2 → 停止剥叶判一下：剩下的点 ≤ 2 就不再剥了。现在剩 3 和 4 两个点（橙色高亮 = 命中中心），它们就是树的中心，循环到此结束。
13. 15返回 [3,4]剥到只剩 3、4，它们就是让树最矮的根。下方「已完成」是删点顺序：先剥外圈 0、1、2、5，最后停在中心 3、4 → 答案 [3,4]。
14. 16n=4 · 中心只有 1 个再看例二 n=4：点 1 在正中央，连着 0、2、3。1 的度数是 3，其余三个点度数都是 1。猜也猜得到中心是 1，剥一圈验证给你看。
15. 17三个度为 1 的点入名单把度为 1 的 0、2、3 全选进本轮名单（橙色）。它们都挂在中心 1 上，这一轮要一起剥掉。
16. 18删 0，中心度数减一剥 0（变绿）。中心 1 掉一条边，度数 3→2，还没到 1，所以 1 这一轮不会成为新叶子。继续剥名单里的 2、3。
17. 19删 2，中心度数再减剥 2（变绿）。1 的度数降到 1，理论上成了新叶子；但本轮名单开始时就定死，1 只会排进下一轮。本轮还剩 3 要剥。
18. 20删 3，中心彻底孤立剥掉本轮最后一个 3（变绿），中心 1 失去全部边、彻底孤立。本轮 0、2、3 全剥完，剩下点数 = 1 ≤ 2，停手。
19. 21返回 [1]只剩 1 一个点，它就是唯一中心 → 答案 [1]。这说明中心可能 1 个也可能 2 个，取决于直径中点落在一个点上还是一条边两端，不看总点数奇偶。
20. 22n=4 链 · 两头度为 1再看一条链 0-1-2-3。两端 0、3 度数为 1 是叶子，中间 1、2 度数为 2。这是会剥出两个中心的经典例子，剥给你看。
21. 23两头一起剥把度为 1 的 0、3 两头 一起选进本轮名单（橙色）。注意是同一轮两个一起剥——这正是「逐个剥会出错」的关键所在。
22. 24删 {0,3} → deg[1]、deg[2] 各减 1两头 0、3 同时剥掉（变绿）。1 和 2 各掉一条边，度数都降到 1，中间只剩 1—2 一条边。剩点 = 2，到停手线。
23. 25返回 [1,2]剩 1、2 两个点 → 答案 [1,2]。试想若一个个剥：先剥 0 再剥 3，1 会先变叶子被误删，最后只剩 2——答案就错了。所以必须整圈一起剥。
24. 26直径中点 = 1 或 2 个点记住这个结论：答案最多 2 个。原理就是树的中心是「最长路径的中点」，中点最多占两个相邻的点。
25. 29拓扑剥叶 = 度数 + 队列凡是「由外向内层层剥、找中心」的树/图题，都能套这个度数 + 队列的剥叶模板。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from collections import deque
class 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)               # 剩下的就是中心

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n <= 2) {
            vector<int> r;
            for (int i = 0; i < n; i++) r.push_back(i);
            return r;
        }
        vector<vector<int>> g(n);
        vector<int> deg(n, 0);
        for (auto& e : edges) {
            g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]);
            deg[e[0]]++; deg[e[1]]++;
        }
        queue<int> leaves;
        for (int i = 0; i < n; i++) if (deg[i] == 1) leaves.push(i);
        int remaining = n;
        while (remaining > 2) {
            int sz = leaves.size();
            remaining -= sz;
            for (int k = 0; k < sz; k++) {
                int u = leaves.front(); leaves.pop();
                for (int v : g[u]) {
                    if (--deg[v] == 1) leaves.push(v);
                }
            }
        }
        vector<int> res;
        while (!leaves.empty()) { res.push_back(leaves.front()); leaves.pop(); }
        return res;
    }
};

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        if (n <= 2) {
            for (int i = 0; i < n; i++) res.add(i);
            return res;
        }
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        int[] deg = new int[n];
        for (int[] e : edges) {
            g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]);
            deg[e[0]]++; deg[e[1]]++;
        }
        Deque<Integer> leaves = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (deg[i] == 1) leaves.offer(i);
        int remaining = n;
        while (remaining > 2) {
            int sz = leaves.size();
            remaining -= sz;
            for (int k = 0; k < sz; k++) {
                int u = leaves.poll();
                for (int v : g.get(u)) {
                    if (--deg[v] == 1) leaves.offer(v);
                }
            }
        }
        while (!leaves.isEmpty()) res.add(leaves.poll());
        return res;
    }
}

复杂度

面试官可能追问