#Problem

#⭐️⭐️⭐️⭐️

题目是说给你N个点. 然后一个2D array表示edges. 要找出所有可能的root结点, 使得这些root结点构成的tree高度最小.

1
2
3
4
5
6
7
8
9
Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
Output: [1]
1
2
3
4
5
6
7
8
9
10
11
Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
Output: [3, 4]

#Solution

思路很显然就是BFS. 算degree, 从degree为1的nodes开始一层层往里推, 直到只有1个或2个结点为止. 剩下2个结点说明他俩都能当root.

所以说隐藏的结论就是最终的output最多只有有个结果.

#Mistake

思路不难想, 但是要实现bug free还是蛮多坑的. 比如平时在BFS的时候while loop的终止条件都是!queue.isEmpty(). 现在的话要怎么退出循环?

  • queue.size() > 2 ?

这个条件的情况下假设给的input是3个结点的tree, 一个root和两个children. 两个children因为degree为1先被加到queue里, 然后呢? 然后while loop就根本不进去了?

这条路不通自然而然想到的一个解决思路就是还是while(!queue.isEmpty()), 然后在里面当queue.size() == 1或者queue.size() == 2的时候break.

但是这样的想法从一开始就是错的. 再仔细想想queue.size()到底是个什么东西? queue.size()是当前这一层degree为1的结点数量, 跟找root有半毛钱关系? 比如O-O-O-O-O这样一个图queue.size一开始就是2, 但能说那俩就是root么?

所以要解决这个问题还是得从本质入手, 我们知道了最终的结果最多是2. 那么我们维护一个num来统计还没有被process过的结点数, 那么当num <= 2的时候, 不就一定能找到答案了么.

#Code

#Java
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
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
final List<Integer> res = new ArrayList<>();
if (n == 0) return res;
if (n == 1) return new ArrayList<>(Arrays.asList(0));
final Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
graph.put(i, new HashSet<>());
}
for (final int [] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
final Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (graph.get(i).size() == 1) {
queue.offer(i);
}
}
int num = n;
while (num > 2) {
final int size = queue.size();
for (int i = 0; i < size; i++) {
final int v = queue.poll();
num--;
for (final int adj : graph.get(v)) {
graph.get(adj).remove(v);
if (graph.get(adj).size() == 1) {
queue.offer(adj);
}
}
}
}
res.addAll(queue);
return res;
}
}

Comments