310.Minimum Height Trees

1-Topological Sort

https://leetcode.com/problems/minimum-height-trees/discuss/76055/

这道题虽然是树的题目，但是跟其最接近的题目是Course Schedule 课程清单和Course Schedule II 课程清单之二。由于LeetCode中的树的题目主要都是针对于二叉树的，而这道题虽说是树但其实本质是想考察图的知识，这道题刚开始在拿到的时候，我最先想到的解法是遍历的点，以每个点都当做根节点，算出高度，然后找出最小的.于是上网看看大家的解法，发现大家推崇的方法是一个类似剥洋葱的方法，就是一层一层的褪去叶节点，最后剩下的一个或两个节点就是我们要求的最小高度树的根节点，这种思路非常的巧妙，而且实现起来也不难，跟之前那到课程清单的题一样，我们需要建立一个图g，是一个二维数组，其中g[i]是一个一维数组，保存了i节点可以到达的所有节点。我们开始将所有只有一个连接边的节点(叶节点)都存入到一个队列queue中，然后我们遍历每一个叶节点，通过图来找到和其相连的节点，并且在其相连节点的集合中将该叶节点删去，如果删完后此节点也也变成一个叶节点了，加入队列中，再下一轮删除。那么我们删到什么时候呢，当节点数小于等于2时候停止，此时剩下的一个或两个节点就是我们要求的最小高度树的根节点啦，参见代码如下：

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if(n <= 1)
            return Arrays.asList(0);
        Set<Integer>[] adj = new Set[n];
        for(int i = 0; i < n; i++)
            adj[i] = new HashSet<>();
        for(int[] e : edges){
            adj[e[0]].add(e[1]);
            adj[e[1]].add(e[0]);
        }

        Deque<Integer> queue = new ArrayDeque<>();
        List<Integer> ans = new ArrayList<>();
        for(int i = 0; i < n; i++){
            if(adj[i].size() == 1)
                queue.offer(i);
        }

        while(!queue.isEmpty()){
            int queueSize = queue.size();
            ans.clear();
            for(int i = 0; i < queueSize; i++){
                // add leaf to ans;
                int leaf = queue.poll();

                ans.add(leaf);

                //add new node to queue;
                for(Integer j : adj[leaf]){
                    adj[j].remove(leaf);
                    if(adj[j].size() == 1)
                        queue.offer(j);
                }
            }
        }
        return ans;

    }
}