310. Minimum Height Trees

/*
Refer: https://leetcode.com/problems/minimum-height-trees/discuss/76055/Share-some-thoughts
Time Complexity: O(N)
Space Complexity: O(N)

N = number of vertices
*/
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n < 1) {
            return new ArrayList<Integer>();
        }
        if (n == 1) {
            return new ArrayList<Integer>(Arrays.asList(0));
        }

        Map<Integer, Set<Integer>> adjacencyMap = new HashMap();
        for (int i = 0; i < n; i++) {
            adjacencyMap.put(i, new HashSet<Integer>());
        }
        for (int[] edge: edges) {
            adjacencyMap.get(edge[0]).add(edge[1]);
            adjacencyMap.get(edge[1]).add(edge[0]);
        }

        Queue<Integer> queue = new LinkedList();
        for (int i = 0; i < n; i++) {
            if (adjacencyMap.get(i).size() == 1) {
                queue.offer(i);
            }
        }

        while (n > 2) {
            int queueSize = queue.size();
            n -= queueSize;
            while (queueSize > 0) {
                int leaf = queue.poll();
                int neighbour = adjacencyMap.get(leaf).iterator().next();
                adjacencyMap.get(neighbour).remove(leaf);
                if (adjacencyMap.get(neighbour).size() == 1) {
                    queue.offer(neighbour);
                }
                queueSize--;
            }
        }

        return new ArrayList<Integer>(queue);
    }
}