Find all root labels such that the tree has minimum height.
Input: n=4, edges=[[1,0],[1,2],[1,3]] → Output: [1]
Input: n=6, edges=[[3,0],[3,1],[3,2],[3,4],[5,4]] → Output: [3,4]
Iteratively remove leaf nodes (degree 1). The remaining 1 or 2 nodes are the centroids.
- Build adjacency list and track degrees
- Add all leaves (degree 1) to queue
- Remove leaves iteratively, updating neighbor degrees
- When remaining nodes <= 2, stop
- Return remaining nodes
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return Collections.singletonList(0);
List<Set<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new HashSet<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
Queue<Integer> leaves = new LinkedList<>();
for (int i = 0; i < n; i++) if (adj.get(i).size() == 1) leaves.add(i);
int remaining = n;
while (remaining > 2) {
int size = leaves.size();
remaining -= size;
for (int i = 0; i < size; i++) {
int leaf = leaves.poll();
int neighbor = adj.get(leaf).iterator().next();
adj.get(neighbor).remove(leaf);
if (adj.get(neighbor).size() == 1) leaves.add(neighbor);
}
}
return new ArrayList<>(leaves);
}
- Time Complexity: O(n)
- Space Complexity: O(n)