Leveled BFS beat 99.74% #Java #BFS

• Please refer to this post for the algorithm details. There is some implementation tricks here to optimize the speed.

``````    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 0) return Collections.emptyList();
else if (n == 1) return Collections.singletonList(0);

// make graph
List<Integer>[] graph = new ArrayList[n];
for(int i=0; i<n; ++i) graph[i] = new ArrayList<>();
int[] degree = new int[n];
for(int[] edge : edges){
int v0 = edge[0], v1 = edge[1];
}

ArrayDeque<Integer> queue = new ArrayDeque<>();
for(int v=0; v<n; v++) {
if (degree[v] == 1) queue.offer(v);
}

int visited = 0;
// level transversal
while(n - visited > 2) {
int size = queue.size();
visited += size;

for(int i=0; i<size; ++i) {
int v = queue.poll();
degree[v] = -1;
for(int nextV : graph[v]) {
if (degree[nextV] == -1) continue;
else if (--degree[nextV] == 1) queue.offer(nextV);
}
}
}

return new ArrayList<Integer>(queue);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.