这条题考的就是对graph和tree的熟悉程度... 记着tree maximum只可能有2个nodes能成为最短path的root... 围绕着这个做文章.. 不停地删leaf..剩下的（小于等于2）的结果就是所要的结果了..
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
| public class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
int degree[] = new int[n];
HashMap<Integer, List<Integer>> nodes = new HashMap<Integer, List<Integer>>();
for (int i = 0; i < edges.length; i++){
int a = edges[i][0];
int b = edges[i][1];
List<Integer> listA = nodes.containsKey(a)?nodes.get(a):new ArrayList<Integer>();
List<Integer> listB = nodes.containsKey(b)?nodes.get(b):new ArrayList<Integer>();
listA.add(b);
listB.add(a);
nodes.put(a, listA);
nodes.put(b, listB);
degree[a]++;
degree[b]++;
}
int remain = n;
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < n; i++){
if(degree[i] == 1) queue.add(i);
}
while (remain > 2){
int size = queue.size();
for (int i = 0; i < size; i++){
int leaf = queue.poll();
remain--;
degree[leaf]--;
for (Integer neighbor:nodes.get(leaf)){
degree[neighbor]--;
if (degree[neighbor] == 1) queue.add(neighbor);
}
}
}
List<Integer> result = new ArrayList<Integer>(queue);
if (n == 1) result.add(0);
return result;
}
}
|
No comments:
Post a Comment