问题描述
给定一个正整数 n 和长度为 n - 1 的二维数组，表示一个图中的 n 个节点和节点之间边的连线，边不重复。这个图可以表示成树的形状，要求找出拥有最小高度的树，返回满足要求的根节点列表。题目链接：点我
样例输入输出
输入：n = 4, edges = [[1,0],[1,2],[1,3]]
输出：[1]
解释：构成的树形状如下，根节点为 1 的树高度最小
输入：n = 1, edges = []
输出：[0]
问题解法
此题最简单的做法是以每个节点为根节点，分别算出其树的高度，然后取最小高度的树的根节点返回。但是这样做会超时。
其实，观察题目意思，可以知道，要想找到最小高度树，可以找到图中的最长路径，然后取这个最长路径上的中间节点作为树的根节点，即是求解的答案。可以使用类似拓扑排序的做法，从边缘节点（度为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
| class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> result = new LinkedList<>();
if (n == 1) {
result.add(0);
return result;
}
int[] degrees = new int[n];
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] edge : edges) {
degrees[edge[0]]++;
degrees[edge[1]]++;
List<Integer> nodes = map.getOrDefault(edge[0], new ArrayList<>());
nodes.add(edge[1]);
map.put(edge[0], nodes);
nodes = map.getOrDefault(edge[1], new ArrayList<>());
nodes.add(edge[0]);
map.put(edge[1], nodes);
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (degrees[i] == 1) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
result.clear();
for (int i = queue.size(); i > 0; i--) {
int current = queue.poll();
result.add(current);
List<Integer> nodes = map.get(current);
for (int node : nodes) {
degrees[node]--;
if (degrees[node] == 1) {
queue.offer(node);
}
}
}
}
return result;
}
}
|
参考资料
https://leetcode.cn/problems/minimum-height-trees/solution/zui-xiao-gao-du-shu-by-leetcode-solution-6v6f
https://leetcode.cn/problems/minimum-height-trees/solution/by-a-fei-8-hm2n