310. Minimum Height Trees

mHT.java

public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if(n==1) {
            List<Integer> x = new ArrayList<Integer>();
            x.add(0);
            return x;
        }
        List<List<Integer>> g = new ArrayList<List<Integer>>(n);
        for(int i=0; i<n; i++){
          g.add(new ArrayList<Integer>());
        }

        int size = n;
        int[] degree = new int[n];
        
        for(int i=0;i<edges.length;i++){
            int x = edges[i][0], y = edges[i][1]; 
            g.get(x).add(y);
            g.get(y).add(x);
            degree[x]++; degree[y]++;
        }

        Deque<Integer> q = new ArrayDeque<Integer>();
        for(int i=0; i<n; i++) {
            if(degree[i]==1){
                q.addLast(i);
            }
        }
        
        while(size>2){
            int sz = q.size();
            for(int j=0; j<sz; j++) {
                int u = q.pollFirst();
                size--;
                for(int i=0; i<g.get(u).size(); i++){
                    int y = g.get(u).get(i);
                    degree[y]--;
                    if(degree[y]==1){
                        q.addLast(y);
                    }                  
                }
            }
        }
        
        List<Integer> mht = new ArrayList<Integer>();
        while(q.size()>0) mht.add(q.pollFirst());
        return mht;
        
    }
}

The minimum height trees are found by removing the leaf vertices one level at a time and working our way up tell we meet at a single vertex or two vertices that share an edge. Therefore there can be 1 or at most 2 root vertices of the minimum height trees.