😲310 minimum height tree

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

在无向树中，叶子结点是度为1的节点，也就是只有一个neighbor，我们逐层剥掉叶子节点，最后一层剩下的1或2个节点就是答案 因为它们类似于图的中心 距离其他节点的平均距离更近

由于是无向图 不区分出度入度，也就不需要indegrees array了

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) {
            return Arrays.asList(n - 1);
        }
        Map<Integer, Set<Integer>> neighbors = new HashMap<>();
        for (int[] edge : edges) {
            Set<Integer> nei = neighbors.get(edge[0]);
            if (nei == null) nei = new HashSet<>();
            nei.add(edge[1]);
            neighbors.put(edge[0], nei);
            nei = neighbors.get(edge[1]);
            if (nei == null) nei = new HashSet<>();
            nei.add(edge[0]);
            neighbors.put(edge[1], nei);
        }
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (neighbors.get(i).size() == 1) queue.offer(i);
        }
        
        while (n > 2) {
            //仍然需要逐层遍历，在每一层结束之后检查n还剩多少
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                int leaf = queue.poll();
                Set<Integer> neis = neighbors.get(leaf);
                for (int nei : neis) {
                    neighbors.get(nei).remove(leaf);
                    if (neighbors.get(nei).size() == 1) queue.offer(nei);
                }
                n--;
            }
        }
        List<Integer> ans = new ArrayList<>();
        while (!queue.isEmpty()) {
            ans.add(queue.poll());
        }
        return ans;
    }
}