-
Notifications
You must be signed in to change notification settings - Fork 0
/
Minimum Height Trees.java
38 lines (36 loc) · 951 Bytes
/
Minimum Height Trees.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
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> leaves = new ArrayList<>();
if (n <= 1) {
leaves.add(0);
return leaves;
}
Map<Integer, Set<Integer>> graph = new HashMap<>();
for(int i = 0; i < n; i++){
graph.put(i, new HashSet<Integer>());
}
for(int[] edge : edges){
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
// find all leaves with size == 1
for (int i = 0; i < n; i++) {
if (graph.get(i).size() == 1) {
leaves.add(i);
}
}
while(n > 2){
List<Integer> newleaves = new ArrayList<>();
for(int leaf : leaves){
for(int adjacent : graph.get(leaf)){
graph.get(leaf).remove(adjacent);
graph.get(adjacent).remove(leaf);
n--;
if (graph.get(adjacent).size() == 1) {
newleaves.add(adjacent);
}
}
}
leaves = newleaves;
}
return leaves;
}