# Java bfs-like AC solution using user defined graph Node class

• ``````public class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
Map<Integer, Node> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
graph.put(i, new Node(i));
}

for (int[] edge : edges) {
graph.get(edge[0]).neighbors.add(graph.get(edge[1]));
graph.get(edge[1]).neighbors.add(graph.get(edge[0]));
graph.get(edge[0]).degree++;
graph.get(edge[1]).degree++;
}

Queue<Node> queue = new LinkedList<>();
for (int index : graph.keySet()) {
if (graph.get(index).degree == 1) {
queue.offer(graph.get(index));
}
}

while (n > 2) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Node leaf = queue.poll();
Node neighbor = leaf.neighbors.iterator().next();
neighbor.neighbors.remove(leaf);//remove leaf from its neighbor's adj list
graph.remove(leaf.label);//remove leaf self
n--;
if (--neighbor.degree == 1) {
queue.offer(neighbor);
}
}
}

return new ArrayList<>(graph.keySet());

}
}

class Node {
int label;
int degree;
Set<Node> neighbors;
public Node(int index) {
label = index;
neighbors = new HashSet<>();
}
}``````

• Inside the bfs-process, when deleting the leaf in its neighbor's adjacent nodes' list, you can just check whether the neighbor's new degree is 1 or not. Instead of looping through the leaf neighbor to find the nodes with degree 1,

• thanks for reminding me! I have modified that.

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