310. Minimum Height Trees

前往題目

之前寫的文章

思路

其實是Hard題目

1. 計算每個node有多少indegree，因為indegree為1的一定是最外圍的node從外圍到中間
2. 計算每個Node的鄰居有誰
3. 從最外圈的Node開始循環，一層一層剝掉，所以indegree要減1
4. 然後如果所有的node都看過了，就把當前node加入到結果，因為他一定是中間的，也就是答案之一
5. 接著看這個node的鄰居，indegree不是0的話就加到queue，做為下一次循環，因為代表他是內圈的node；如果indegree是0就代表該node已經在result裡了

Code

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        // Base case
        List<Integer> list = new ArrayList<>();
        if (edges.length == 0) {
            list.add(0);
            return list;
        }
        
        // Indegree of every node
        int[] indegree = new int[n];

        // save adjacent nodes of certain node into a HashMap
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();

        for (int i = 0; i < n; i++) map.put(i, new ArrayList<>());
        
        // Build degree counts and neighbors of each node
        for (int[] edge : edges) {
            indegree[edge[0]]++;
            indegree[edge[1]]++;
            map.get(edge[0]).add(edge[1]);
            map.get(edge[1]).add(edge[0]);
        }
        
        // if indegree of a node is 1, it means that the node only has one adjacent node 
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) if (indegree[i] == 1) q.offer(i);
        
        // count the number of nodes which has been watched
        int count = 0;
        while (! q.isEmpty()) {
            int size = q.size();
            count += size;
            for (int i = 0; i < size; i++) {
                int id = q.poll();
                indegree[id]--;
                // if count == n, add the id of node into the resulting list
                if (count == n) list.add(id);
                for (int adjId : map.get(id)) {
                    // if indegree of a node equals to 0, it means this node has already been added into the result list
                    if (indegree[adjId] != 0) {
                        indegree[adjId]--;
                        if (indegree[adjId] == 1) q.offer(adjId);
                    }
                }
            }
        }
        return list;
    }
}