[LeetCode] 310. Minimum Height Trees

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

The entire process is like peeling an onion.  Keep removing vectors only has 1 edge until the graph has less than 2 vectors left. Return the remaining vectors as the root of MHTs.

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {   
        int[] degree = new int[n];
        Map<Integer, List<Integer>> graph = new HashMap();
        
        // construct the graph
        for (int i = 0; i < edges.length; i++) {
            int a = edges[i][0];
            int b = edges[i][1];
            
            if (!graph.containsKey(a)) {
                graph.put(a, new ArrayList<Integer>());
            }
            
            if (!graph.containsKey(b)) {
                graph.put(b, new ArrayList<Integer>());
            }
            
            graph.get(a).add(b);
            graph.get(b).add(a);
            
            degree[a] += 1;
            degree[b] += 1;
        }
        
        // start to peel the onion
        Queue<Integer> queue = new LinkedList();
        boolean[] deleted = new boolean[n];
        int remains = n;
        
        for (int i = 0; i < n; i++) {
            // put all nodes on outline to the queue
            if (degree[i] <= 1) {
                queue.offer(i);
            }
        }
        
        // peel the onion until less than 2 nodes are left
        // a MHT can have 2 possible roots in maximum
        while (remains > 2) {
            int size = queue.size();
            // use for-loop to ensure peel all nodes on current layer
            for (int i = 0; i < size; i++) {
                // peel the node off the tree
                int a = queue.poll();
                deleted[a] = true;
                degree[a] -= 1;
                remains -= 1;

                for (int b : graph.get(a)) {
                    if (deleted[b]) {
                        continue;
                    }

                    // put its peer to queue if the peer node is on the next layer
                    degree[b] -= 1;
                    if (degree[b] == 1) {
                        queue.offer(b);
                    }
                }
            }
        }
        
        // nodes on the last layer are MHT's root 
        return new ArrayList<Integer>(queue);
    }
}

Edited on 12/16/2021. Replace with Java solution.