企业官网建设流程全解析

这道题的核心思路是拓扑排序（剥洋葱法）。最小高度树的根节点一定位于无向图的“中心”，我们可以通过不断删除度为 1 的叶子节点，最后剩下的 1 个或 2 个节点就是答案。

思路解析

1. 建图与统计度数：将 edges 转化为邻接表，并记录每个节点的度数。
2. 初始化队列：将所有度数为 1 的叶子节点加入队列。
3. 层层剥离：每次取出当前层的所有叶子节点，将其从图中“删除”（即减少邻居节点的度数）。如果某个邻居节点的度数因此变为 1，则将其加入下一轮的队列。
4. 终止条件：当剩余节点数 ≤ 2 时，队列中剩下的节点即为最小高度树的根。

Java 代码实现

import java.util.*;

class Solution {
public List findMinHeightTrees(int n, int[][] edges) {
List result = new ArrayList<>();
if (n == 1) {
result.add(0);
return result;
}

// 1. 构建邻接表和度数数组 List<Set<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new HashSet<>()); } int[] degree = new int[n]; for (int[] edge : edges) { int u = edge[0], v = edge[1]; adj.get(u).add(v); adj.get(v).add(u); degree[u]++; degree[v]++; } // 2. 将初始的叶子节点（度数为1）加入队列 Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < n; i++) { if (degree[i] == 1) { queue.offer(i); } } // 3. 层层剥离叶子节点 int remainingNodes = n; while (remainingNodes > 2) { int size = queue.size(); remainingNodes -= size; // 减去当前层的叶子节点数 for (int i = 0; i < size; i++) { int leaf = queue.poll(); // 遍历当前叶子节点的邻居 for (int neighbor : adj.get(leaf)) { degree[neighbor]--; // 删除叶子节点，邻居度数减1 if (degree[neighbor] == 1) { queue.offer(neighbor); // 如果邻居变成新的叶子，加入队列 } } } } // 4. 队列中剩下的节点即为答案 result.addAll(queue); return result; }

}

复杂度分析

• 时间复杂度：O(n)，每个节点和边最多被访问常数次。
• 空间复杂度：O(n)，用于存储邻接表和度数数组。

关键点总结

• 为什么最后只剩 1 或 2 个节点？ 因为树的最长路径（直径）的中点最多只有 2 个。
• 使用 Set 存储邻接表：方便快速删除边（虽然本题只需减少度数，但 Set 在需要实际删除边时更高效）。
• 层序遍历的思想：每次处理一整层叶子节点，确保同步剥离。

需要顺带看看用 DFS 求直径中点的解法吗？两种思路对比着看会更透彻。