友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
310. 最小高度树
树是一个无向图，其中任何两个顶点只通过一条路径连接。换句话说，任何一个没有简单环路的连通图都是一棵树。
给你一棵包含 n 个节点的树，标记为 0 到 n - 1。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [a~i~, b~i~] 表示树中节点 ai 和 bi 之间存在一条无向边。
可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
示例 1：
输入：n = 4, edges = [[1,0],[1,2],[1,3]] 输出：[1] 解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。
示例 2：
输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] 输出：[3,4]
提示：
-
1 <= n <= 2 * 104 -
edges.length == n - 1 -
0 <= ai, bi < n+ -
ai != bi -
所有
(ai, bi)互不相同 -
给定的输入 保证 是一棵树，并且 不会有重复的边
思路分析
首先先到的解法是深度优先搜索，先构建出来这个图，然后遍历每个节点，找出以每个节点为根的最大高度，最后返回高度最小的节点列表。加上备忘录优化，通过 68 / 71 测试用例。
边缘节点是不可能产生最小高度的树的，只有靠近中间的节点才具有生产最小高度的树的可能。看题解，可以从周围向中间聚集，使用广度优先遍历，每次只遍历度为 1 的节点，遍历到的节点，度减一，这样就实现了向中间靠拢。网友说，这是剪窗花思路。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* 优化后：使用广度优先搜索，从外向内聚拢，中间节点才能生成最小高度树。
*
* 优化前：深度优先遍历，通过 68 / 71 测试用例。
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-07-10 17:37:37
*/
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) {
return Arrays.asList(0);
}
int[] degrees = new int[n];
List<Integer>[] children = new List[n];
for (int[] edge : edges) {
degrees[edge[0]]++;
degrees[edge[1]]++;
if (children[edge[0]] == null) {
children[edge[0]] = new ArrayList<>();
}
children[edge[0]].add(edge[1]);
if (children[edge[1]] == null) {
children[edge[1]] = new ArrayList<>();
}
children[edge[1]].add(edge[0]);
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (degrees[i] == 1) {
queue.add(i);
}
}
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
int size = queue.size();
result = new ArrayList<>();
for (int i = 0; i < size; i++) {
int cur = queue.poll();
result.add(cur);
List<Integer> child = children[cur];
for (Integer node : child) {
degrees[node]--;
if (degrees[node] == 1) {
queue.add(node);
}
}
}
}
return result;
}