LeetCode 310. 最小高度树

2026-06-11 HGNULB 约 10 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 310. 最小高度树

题意分析

给定 n 个编号从 0 到 n - 1 的节点和 n - 1 条无向边，且整个图连通。要求选出所有这样的节点：以它为根把这棵无根树立起来时，树的高度是所有选法中最小的。返回全部这样的根。

「n - 1 条边 + 连通」是一个强约束信号，它把图的形态锁死为一棵树：无环、任意两点之间恰有一条路径。这意味着不需要处理重边、自环，也不需要判环。

输入以边列表给出，且边是无向的，所以建图时每条边必须同时写进两个端点的邻接表，度数也要在两端各加一。这是无向图题目最常见的落点。

规模上 n 可达 $2 \times 10^4$，配合边数同阶，只能接受线性或接近线性的做法，逐个节点试根的平方级方案会超时。

边界要特别小心两个极小规模：n == 1 时一条边都没有，所有节点的度数都是 0，任何依赖「度数为 1」的初始化都会得到空集合；n == 2 时两个节点互为叶子，答案是它们两个而不是其中一个。此外链状的树是最容易暴露层次处理错误的形态。

解法：拓扑剥离叶子

核心思路

最直接的想法是枚举根：对每个节点各做一次遍历求出树高，取最小值再收集所有达到最小值的节点。这个做法思路上无懈可击，但代价是 $n$ 次遍历，总共 $O(n^2)$，在两万个节点的规模上不可行。

瓶颈在于这 $n$ 次遍历彼此完全独立，每次都把整棵树重新走了一遍，没有复用任何结构信息。

换个角度看「以某点为根的树高」这个量：它其实就是该点到树上最远节点的距离，图论里称为偏心距。要找的就是偏心距最小的点，也就是树的中心。而树的中心有一条经典性质——它一定落在树的最长路径（直径）的中点上；直径长度为偶数时中点是一个节点，为奇数时中点落在一条边上、对应两个节点。所以答案的个数只可能是 1 或 2，绝不会更多。

直接求直径再取中点是可行的（两次广度优先即可），但还有一条实现更短的路：从最外层往里剥。每一轮同时删掉当前所有的叶子节点，相当于把直径的两端各截掉 1 个单位；反复剥下去，直径不断缩短，最后剩下的 1 个或 2 个节点就是中点，也就是答案。

这个过程维持的不变量是：每一轮剥离结束后，剩下的节点仍然构成一棵连通的树，且它的中心与原树的中心完全一致——因为被删掉的都是距离中心最远的一层，删掉它们不会改变谁离两端最平衡。循环在剩余节点数不超过 2 时停止，此时队列里未被删除的节点就是全部答案。

解题步骤

先特判 n == 1，直接返回 [0]。单点树没有任何边，度数全为 0，后面所有依赖「度数为 1」的逻辑都会落空，必须在入口处挡掉。

建立邻接表并统计度数。因为边是无向的，每条边要在两个端点的邻接表里各加一次，两端的度数也各加一。漏掉一个方向会让部分节点永远等不到被处理。

把所有度数为 1 的节点放进队列，作为第一层叶子。度数为 1 正是「叶子」在无根树里的定义，它替代了有向图拓扑排序中「入度为 0」的角色。

用 remaining 记录尚未被删除的节点数，只要 remaining > 2 就继续剥。这里的判据必须是剩余节点数而不是队列是否为空——用队列非空当条件，会连中心自己也一起删光，最后返回空集。

每一轮先把当前队列长度记为 size，然后恰好弹出 size 个节点，并让 remaining 一次性减去 size。这保证一轮只处理「当前这一层」的叶子，本轮新产生的叶子留到下一轮。长度必须在循环前固定，否则新入队的节点会被卷进本层。

对每个弹出的叶子，把它所有邻居的度数减一；某个邻居的度数恰好变成 1 时，说明它在这一轮之后成了新叶子，入队等待下一轮。判据要用「恰好等于 1」而不是「小于等于 1」，否则度数降到 0 的中心节点会被重复入队。

循环结束后，队列里剩下的就是全部答案。

以 n = 6、edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] 走一遍：建图后度数为 degree[0] = 1、degree[1] = 1、degree[2] = 1、degree[3] = 4、degree[4] = 2、degree[5] = 1。初始队列装入所有度数为 1 的节点，即 [0, 1, 2, 5]，remaining = 6。进入循环：6 > 2 成立，本轮 size = 4，remaining 减为 2。逐个处理——弹出 0，邻居 3 的度数由 4 降到 3，不等于 1；弹出 1，度数 3 降到 2，不等于 1；弹出 2，度数 2 降到 1，恰好成为新叶子，节点 3 入队；弹出 5，邻居 4 的度数由 2 降到 1，节点 4 入队。本轮结束，队列变成 [3, 4]。再判循环条件，remaining = 2 不大于 2，退出。返回队列中的 [3, 4]，与预期一致——以 3 或 4 为根时树高都是 2，换成任何其他节点树高至少是 3。

代码实现

class Solution {
    // 从所有叶子开始一层层删除，相当于从外向内收缩树的半径。
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        if (n == 1) {
            res.add(0);
            return res;
        }

        List<Integer>[] graph = new List[n];
        int[] degree = new int[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            graph[u].add(v);
            graph[v].add(u);
            degree[u]++;
            degree[v]++;
        }

        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                queue.offer(i);
            }
        }

        int remaining = n;
        while (remaining > 2) {
            int size = queue.size();
            remaining -= size;
            for (int i = 0; i < size; i++) {
                int leaf = queue.poll();
                for (int next : graph[leaf]) {
                    degree[next]--;
                    if (degree[next] == 1) {
                        queue.offer(next);
                    }
                }
            }
        }

        res.addAll(queue);
        return res;
    }
}

func findMinHeightTrees(n int, edges [][]int) []int {
    // 从所有叶子开始一层层删除，相当于从外向内收缩树的半径。
    if n == 1 {
        return []int{0}
    }

    graph := make([][]int, n)
    degree := make([]int, n)
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
        degree[u]++
        degree[v]++
    }

    queue := make([]int, 0)
    for i := 0; i < n; i++ {
        if degree[i] == 1 {
            queue = append(queue, i)
        }
    }

    remaining := n
    head := 0
    for remaining > 2 {
        size := len(queue) - head
        remaining -= size
        for i := 0; i < size; i++ {
            leaf := queue[head]
            head++
            for _, next := range graph[leaf] {
                degree[next]--
                if degree[next] == 1 {
                    queue = append(queue, next)
                }
            }
        }
    }

    return queue[head:]
}

复杂度分析

时间复杂度：$O(n)$，建图遍历 $n - 1$ 条边；剥离阶段每个节点至多入队一次、出队一次，出队时会扫描它的邻接表，所有邻接表长度之和是边数的两倍，因此总代价仍是线性。

空间复杂度：$O(n)$，邻接表保存 $2(n-1)$ 个方向、度数数组长度 $n$、队列最多同时容纳 $n$ 个节点，三者都是线性量级。

关键点总结

「以某点为根的树高」等价于该点的偏心距，最小偏心距的点就是树的中心；中心必落在直径中点上，所以答案的个数只可能是 1 或 2。先把结论想清楚，才知道循环该在什么时候停。

从外向内层层剥离是无根树问题的通用手段。它和有向图按入度剥离共用同一套按层出队的框架，只是判据从「入度为 0」换成了「度数为 1」。

循环条件必须写成「剩余节点数 > 2」。用队列是否为空作条件，会把中心节点自己也当作最后一层叶子删掉，最终返回空集。

按层处理时要先固定本轮队列长度。边遍历边取长度会把本轮新产生的叶子卷进当前层，层次错乱后 remaining 也跟着失真。

面试视角：几乎必然被追问「为什么答案最多两个」。要给出直径论证——若存在三个偏心距同时最小的点，就能拼出一条比直径更长的路径，与直径的定义矛盾。能讲这一步，说明你不是在背模板。

面试视角：可以主动提出等价方案「两次广度优先求出直径再取中点」，并对比取舍：两种做法复杂度相同，剥叶子的实现更短、边界更少，而求直径的写法更能直接解释答案的来源。展示两条路径并说明为何选其一，是图论题上的加分表达。

易错点总结

错误写法：不特判 n == 1。用例 n = 1、edges = [] → 唯一节点的度数是 0，初始队列为空，remaining = 1 不满足循环条件，直接返回空列表，正确答案是 [0]。

错误写法：循环条件写成「队列非空」。用例 n = 2、edges = [[0,1]] → 两个节点度数都是 1，全部入队后被一次剥光，返回空列表，正确答案是 [0, 1]。

错误写法：不按层处理，每次只弹一个节点并让 remaining 减 1。用例 n = 4、edges = [[0,1],[1,2],[1,3]] → 删掉 0 后 remaining = 3，删掉 2 后 remaining = 2 立刻停止，队列里留着尚未处理的 3 和新入队的 1，返回 [3, 1]，正确答案是 [1]。

错误写法：本层长度不预先固定，直接在循环条件里调用队列长度。用例 n = 6、edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] → 本轮新入队的 3 和 4 被当成同层继续删除，队列被清空，返回空列表，正确答案是 [3, 4]。

错误写法：建图时只写单向边、度数也只加一端。用例 n = 3、edges = [[0,1],[1,2]] → 得到的度数是 [1, 1, 0]，节点 2 因度数为 0 永远不会入队，剥离过程完全错位，正确答案是 [1]。

错误写法：新叶子的判据写成 degree[next] <= 1。用例 n = 4、edges = [[0,1],[1,2],[1,3]] → 中心节点 1 的度数依次降为 2、1、0，在降到 1 和降到 0 时各入队一次，返回 [1, 1]，答案里出现重复。

错误写法：认为最小高度树一定唯一，只返回队列里的第一个节点。用例 n = 2、edges = [[0,1]] → 只返回 [0]，漏掉同样合法的 1。

错误写法：凭直觉认为度数最大的节点就是答案。用例 n = 6、edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] → 度数最大的是节点 3，只返回 [3]，漏掉同样能达到最小高度的节点 4。

相似题目

题目	难度	考察点
207. 课程表	中等	有向图判环，只需回答能否全部完成，无需输出任何顺序
210. 课程表 II	中等	按入度剥离并输出一条完整的拓扑序，剥离方向从入口而非外围开始
269. 火星词典	困难	难点在从相邻单词对推出边，还要识别前缀矛盾这种非法输入
444. 序列重建	中等	要判定拓扑序是否唯一，队列中同时出现两个候选即说明不唯一
1462. 课程表 IV	中等	需要回答任意两点的可达性，要在拓扑过程中维护传递闭包
LCR 113. 课程表 II	中等	与 210 同题，适合拿来对比广度优先剥离与深度优先逆后序两种写法
LCR 114. 火星词典	困难	与 269 同题，可用于练习建图时字符集合的初始化细节
LCR 115. 序列重建	中等	与 444 同题，重点在唯一性判定而非合法性判定
面试题 04.01. 节点间通路	中等	只需判断两点是否连通，一次深度或广度优先搜索即可，不涉及层次剥离