05 August 2008
给一堆二维数组，表示edges，返回最小高度树
首先，我们看了样例，发现这个树并不是二叉树，是多叉树。
然后，我们可能想到的解法是：根据题目的意思，就挨个节点遍历bfs，统计下每个节点的高度，然后用map存储起来，后面查询这个高度的集合里最小的就可以了。
但是这样会超时的。
于是看图（题目介绍里面的图）分析一下，发现，越是靠里面的节点越有可能是最小高度树。
所以，可以这样想，我们可以倒着来。
从边缘开始，先找到所有出度为1的节点，然后把所有出度为1的节点进队列，然后不断地bfs，最后找到的就是两边同时向中间靠近的节点，那么这个中间节点就相当于把整个距离二分了，那么它当然就是到两边距离最小的点啦，也就是到其他叶子节点最近的节点了。
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
52
53
54
55
56
57
58
59
60
61
62
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class FindMinHeightTrees {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> res = new ArrayList<>();
/*如果只有一个节点，那么他就是最小高度树*/
if (n == 1) {
res.add(0);
return res;
}
/*建立各个节点的出度表*/
int[] degree = new int[n];
/*建立图关系，在每个节点的list中存储相连节点*/
List<List<Integer>> map = new ArrayList<>();
for (int i = 0; i < n; i++) {
map.add(new ArrayList<>());
}
for (int[] edge : edges) {
degree[edge[0]]++;
degree[edge[1]]++;/*出度++*/
map.get(edge[0]).add(edge[1]);/*添加相邻节点*/
map.get(edge[1]).add(edge[0]);
}
/*建立队列*/
Queue<Integer> queue = new LinkedList<>();
/*把所有出度为1的节点，也就是叶子节点入队*/
for (int i = 0; i < n; i++) {
if (degree[i] == 1) queue.offer(i);
}
/*循环条件当然是经典的不空判断*/
while (!queue.isEmpty()) {
res = new ArrayList<>();/*这个地方注意，我们每层循环都要new一个新的结果集合，
这样最后保存的就是最终的最小高度树了*/
int size = queue.size();/*这是每一层的节点的数量*/
for (int i = 0; i < size; i++) {
int cur = queue.poll();
res.add(cur);/*把当前节点加入结果集，不要有疑问，为什么当前只是叶子节点为什么要加入结果集呢?
因为我们每次循环都会新建一个list，所以最后保存的就是最后一个状态下的叶子节点，
这也是很多题解里面所说的剪掉叶子节点的部分，你可以想象一下图，每层遍历完，
都会把该层（也就是叶子节点层）这一层从队列中移除掉，
不就相当于把原来的图给剪掉一圈叶子节点，形成一个缩小的新的图吗*/
List<Integer> neighbors = map.get(cur);
/*这里就是经典的bfs了，把当前节点的相邻接点都拿出来，
* 把它们的出度都减1，因为当前节点已经不存在了，所以，
* 它的相邻节点们就有可能变成叶子节点*/
for (int neighbor : neighbors) {
degree[neighbor]--;
if (degree[neighbor] == 1) {
/*如果是叶子节点我们就入队*/
queue.offer(neighbor);
}
}
}
}
return res;/*返回最后一次保存的list*/
}
}