-
Notifications
You must be signed in to change notification settings - Fork 0
/
MinimumHeightTrees.java
38 lines (37 loc) · 1.33 KB
/
MinimumHeightTrees.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
/* https://leetcode.com/problems/minimum-height-trees/submissions/1239858288/?envType=daily-question&envId=2024-04-23 */
/* 310. Minimum Height Trees */
class MinimumHeightTrees {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if(n==0 || edges.length==0){
return new ArrayList<>(Arrays.asList(0));
}
List<Integer> ans = new ArrayList<>();
Map<Integer,Set<Integer>> graph = new HashMap<>();
for(int i=0;i<n;i++)
graph.put(i,new HashSet<>());
for(int[] edge: edges){
final int u = edge[0];
final int v = edge[1];
graph.get(u).add(v);
graph.get(v).add(u);
}
for(Map.Entry<Integer,Set<Integer>> entry: graph.entrySet()){
final int label = entry.getKey();
Set<Integer> children = entry.getValue();
if(children.size()==1)
ans.add(label);
}
while(n>2){
n-=ans.size();
List<Integer> nextLeaves = new ArrayList<>();
for(final int leaf : ans){
final int u = (int) graph.get(leaf).iterator().next();
graph.get(u).remove(leaf);
if(graph.get(u).size()==1)
nextLeaves.add(u);
}
ans=nextLeaves;
}
return ans;
}
}