Minimum Height Trees

1public List<Integer> findMinHeightTrees(int n, int[][] edges) {
2    if (n == 1) return Collections.singletonList(0);
3
4    // Build adjacency list and degree
5    List<Set<Integer>> adj = new ArrayList<>();
6    int[] degree = new int[n];
7
8    for (int i = 0; i < n; i++) {
9        adj.add(new HashSet<>());
10    }
11    for (int[] edge : edges) {
12        adj.get(edge[0]).add(edge[1]);
13        adj.get(edge[1]).add(edge[0]);
14        degree[edge[0]]++;
15        degree[edge[1]]++;
16    }
17
18    // Find initial leaves (degree = 1)
19    List<Integer> leaves = new ArrayList<>();
20    for (int i = 0; i < n; i++) {
21        if (degree[i] == 1) leaves.add(i);
22    }
23    int remaining = n;
24
25    // Remove leaves layer by layer
26    while (remaining > 2) {
27        List<Integer> newLeaves = new ArrayList<>();
28
29        for (int leaf : leaves) {
30            for (int neighbor : adj.get(leaf)) {
31                degree[neighbor]--;
32                adj.get(neighbor).remove(leaf);
33                if (degree[neighbor] == 1) {
34                    newLeaves.add(neighbor);
35                }
36            }
37        }
38
39        remaining -= leaves.size();
40        leaves = newLeaves;
41    }
42
43    return leaves;
44}