310. Minimum Height Trees

這題還是挺難的

關鍵是從leaf出發

indegree[edge[0]]+＋
indegree[edge[1]]++;

還要考慮這個問題

T: O(|V|)

S: O(|V|)

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) { // edge case, only has root
            return Arrays.asList(0);
        }
        if (n == 2) { // edge case, only has root
            return Arrays.asList(0, 1);
        }
        
        List<Integer>[] graph = new ArrayList[n];
        int[] indegree = new int[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // this is a undirected graph
        for (int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
            indegree[edge[0]]++;
            indegree[edge[1]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            // this is specail, in this problem, the most far and out node, indegree is 1
            if (indegree[i] == 1) {
                queue.offer(i);
            }
        }
        
        boolean[] visited = new boolean[n];
        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int q = 0; q < size; q++) {
                int cur = queue.poll();
                count++;
                visited[cur] = true;
                
                for (int next : graph[cur]) {
                    indegree[next]--;
                    if (indegree[next] == 1) {
                        queue.offer(next);
                    }
                }
            }
            // when only left core node, can be the root node
            // the count will be n-1 or n-2
            if (count == n-1 || count == n-2) {
                break;
            }
        }
        
        // add un-visited core node (root)
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                res.add(i);
            }
        }
        return res ;
    }
}

/*
Return a list of all MHTs' root labels.

so find root to create the min height

use topology sort, but 最外層的 node 入度為1
*/

```java
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) {
            return Arrays.asList(0);
        }
        if (n == 2) {
            return Arrays.asList(0, 1);
        }
        int[] indegree = new int[n];
        List<List<Integer>> tree = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            tree.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            tree.get(edge[0]).add(edge[1]);
            tree.get(edge[1]).add(edge[0]);
            indegree[edge[0]]++;
            indegree[edge[1]]++;
        }
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 1) {
                queue.offer(i);
            }
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int q = 0; q < size; q++) { 
                // must level by level!, 因為是一層一層去扒開的, 要走完, 不然可能會多 node
                // 因為 n-1 or n-2 都符合, 所以除非 n-1, n-2 都在同一層(都在 root), 不然應該 n-2 可能不是 root
                int curr = queue.poll();
                if (visited[curr]) {
                    continue;
                }
                count++;
                visited[curr] = true;
                for (int next : tree.get(curr)) {
                    indegree[next]--;
                    if (indegree[next] == 1) {
                        queue.offer(next);
                    }
                }
            }
            if (count == n - 1 || count == n-2) {
                break;
            }
        }

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                result.add(i);
            }
        }
        return result;
    }
}
```