Minimum Height Trees

lc310 For an undirected graph with tree characteristics, we can choose any node as the root. The resulting graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3

return [1]

这个题一开始想的是brute force的方法解决，就是任意每一个node当root的起点，然后求解，但是这样做非常麻烦。然后看到了Leetcode上的解法，竟然转化成了topological sorting的方法，就是说从每个直邮一个index出来的点，那么这些点一定是leaf，然后从这些点开始bfs往里面扫，当最后只剩下2个点的时候，这两个点就是root。他的方法用的不是hashmap是linkedlist＋set ，说这样可以省空间，我就自己试着改写了一下喝以前coursesechedule一样的方法。

public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(0);
        HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        int[] degree = new int[n];
        for (int i = 0; i < n; ++i) 
            map.put(i, new ArrayList<Integer>());       
        for (int[] edge : edges) {
            map.get(edge[0]).add(edge[1]);
            map.get(edge[1]).add(edge[0]);
            degree[edge[0]]++;
            degree[edge[1]]++;
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < n; ++i){
            if(degree[i] == 1){
                queue.offer(i);
            }
        }

        while(n > 2 ){
            n -= queue.size();
            int k = queue.size();
            for(int j = 0; j < k; j++){
                int cur = queue.poll();
                int i = map.get(cur).get(0);
                map.remove(cur);
                List<Integer> list = map.get(i);
                list.remove((Integer)cur);
                if(list.size() == 1) queue.offer(i);

            }
        }
        return new ArrayList(queue);

    }
}