310. Minimum Height Trees

    /*
     * 310. Minimum Height Trees
     * 2016-3-29 by Mingyang
     * 同样的方法构建无向图
     * 既用了indegree的array，也用了HashMap来存点，采用了层层剥丝的方法
     * 先从最外围的节点开始，一个一个的把互相的入度减一，当入度减为1的时候就可以加入新的一层
     * 最后剩下的就是最后的点
     * 因为这里是无向图，所以从子节点很容易找到自己的父节点，因为子指向父，父指向子，相对于
     * 有向图要简单点
     */

     public static List<Integer> findMinHeightTrees(int n, int[][] edges) {
            if (n == 1) return Collections.singletonList(0);
            List<Set<Integer>> adj = new ArrayList<>(n);
            for (int i = 0; i < n; ++i) adj.add(new HashSet<Integer>());
            for (int[] edge : edges) {
                adj.get(edge[0]).add(edge[1]);
                adj.get(edge[1]).add(edge[0]);
            }
            Queue<Integer> queue = new LinkedList<Integer>();
            for (int i = 0; i < n; ++i)
                if (adj.get(i).size() == 1){ 
                    queue.add(i);
                }
            while (n > 2) {
                 n-=queue.size();
                 int size=queue.size();
                for (int i=0;i<size;i++) {
                    int temp=queue.poll();
                    int j = adj.get(temp).iterator().next();
                    adj.get(j).remove(temp);
                    if (adj.get(j).size() == 1){ 
                       queue.add(j);
                    }
                }
            }
            List<Integer> res=new ArrayList<Integer>();
            while(!queue.isEmpty()){
                res.add(queue.poll());
            }
            return res;
     }