> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/topology/310.-minimum-height-trees.md).

# 310. Minimum Height Trees

這題還是挺難的

關鍵是從leaf出發

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

還要考慮這個問題

<figure><img src="https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2F9UCqMamVgWNFNTa6ZJqM%2Fimage.png?alt=media&amp;token=789c2add-b487-4d95-a0cd-9df994f79256" alt=""><figcaption></figcaption></figure>

T: O(|V|)

S: O(|V|)

```java
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
```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;
    }
}
```
````