LeetCode 310. 最小高度树
题目描述
题意分析
给定一棵无向树，可以选择任意节点作为根。以某节点为根时，树高是它到最远节点的距离，按边数计算；要求找出能让这个最大距离最小的所有根节点编号，返回顺序不限。
输入保证连通、无环，共有
n个节点和n - 1条边，不需要删边或改变树形。改变的只是根的位置。最优根可能有一个，也可能有相邻的两个，不能只返回某个候选或最小高度数值。
解法：拓扑剥离叶子
核心思路
[!blue]
树超过两个节点时，叶子不会是最优根。若把根从叶子移到它唯一的邻居，到其他节点的路径都少一条边；到原叶子的距离虽然变成一，但原树至少还有第三个节点，整体最大距离仍会下降。因此可以先排除当前所有叶子。
同时删去一整层叶子后，对每个留下的节点而言，它到最远处的距离都恰好减少一：最远节点一定是叶子，去掉它后，通向它的父节点仍在剩余树中。所有候选的高度都减去相同值，谁更优的相对关系不变，所以可以继续在剩余树上重复这个过程。
这样不断从外向内剥离，最后留下一个或两个节点，就是树的中心。一个节点时它是唯一最优根；两个相连节点时二者处在同样居中的位置，都是答案。这也对应树的最长路径中间位置。
用邻接表记录连接关系，
degree表示节点当前剩余连接数量。初始把度数为一的节点放入队列；每删除一个叶子，就降低其邻居的度数，邻居首次降到一时成为下一层叶子，加入队列。每轮开始必须固定本层叶子数量
size，整体扣除这批节点，再处理它们。新出现的叶子只能等到下一轮，不能刚剩两个就中断本轮，否则会留下未对称剥离的节点。只在整轮结束后检查remaining > 2。单节点树没有度数为一的叶子，需要直接返回零号节点。最后一轮中，唯一中心的度数可能先降到一而入队，再因其他叶子删除降到零；它仍应保留为答案，因此只在首次等于一时入队，不要求最后仍保持度数一。
解题步骤
n == 1时直接返回唯一节点零。- 建立无向邻接表并统计度数，将所有度数为一的节点入队。
- 令
remaining = n；剩余超过两个节点时，固定本轮队列中的叶子数。- 整体扣除这批叶子，逐个降低邻居度数；首次降为一的邻居加入下一层。
- 剩余一或两个节点时停止，返回队列中尚未处理的节点。
代码实现
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)$，邻接表、度数数组和队列都与节点数同阶。
关键点总结
[!green]
- 当前叶子作为根不如它的邻居，而同步去掉所有叶子不会改变剩余候选的优劣关系。
- 一轮代表同一层的完整剥离，下一层不能提前混入。
- 停在一个或两个中心，单节点与最终度数降到零的中心都要正确保留。
易错点总结
[!yellow]
- 不断处理直到队列为空，会把应当返回的中心也删除。
- 边删边看到剩余两个就立刻停止，可能只删除了本层的一部分，破坏同步剥离。
- 使用不断增长的队列长度控制当前层，会把新叶子提前删除。
- 度数小于等于一就反复入队，可能重复加入同一节点；只在首次降到一时加入。
- 忽略
n == 1，会因为找不到度数为一的节点而返回空答案。- 只取队首一个结果，会漏掉双中心情况。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 543. 二叉树的直径 | 简单 | 树的最小高度根位于直径中心，可从最长路径理解不断剥叶子的正确性。 |