# 310. Minimum-Height-Trees

difficulty: Medium

A tree is an undirected graph in which any two vertices are connected by *exactly* one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of `n` nodes labelled from `0` to `n - 1`, and an array of `n - 1` `edges` where `edges[i] = [ai, bi]` indicates that there is an undirected edge between the two nodes `ai` and `bi` in the tree, you can choose any node of the tree as the root. When you select a node `x` as the root, the result tree has height `h`. Among all possible rooted trees, those with minimum height (i.e. `min(h)`)  are called **minimum height trees** (MHTs).

Return *a list of all **MHTs'** root labels*. You can return the answer in **any order**.

The **height** of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/09/01/e1.jpg)

<pre><code><strong>Input: n = 4, edges = [[1,0],[1,2],[1,3]]
</strong><strong>Output: [1]
</strong><strong>Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.
</strong></code></pre>

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/09/01/e2.jpg)

<pre><code><strong>Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
</strong><strong>Output: [3,4]
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: n = 1, edges = []
</strong><strong>Output: [0]
</strong></code></pre>

**Example 4:**

<pre><code><strong>Input: n = 2, edges = [[0,1]]
</strong><strong>Output: [0,1]
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= n <= 2 * 104`
* `edges.length == n - 1`
* `0 <= ai, bi < n`
* `ai != bi`
* All the pairs `(ai, bi)` are distinct.
* The given input is **guaranteed** to be a tree and there will be **no repeated** edges.

## Method One

```Java
class Solution {
    /*
    这个讨论的最高评论直接杀死比赛，解释了一切。
    https://leetcode.com/problems/minimum-height-trees/discuss/76055/Share-some-thoughts
    我们用 indegrees 找到所有的 leaf, 然后同时开始BFS。
    我们每次记录上一层BFS 的 leaves, 这样我们最后一层 BFS 的 leaves 就是所有的正确答案了。
    */
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if( n == 0){
            return new ArrayList<Integer>();
        }
        if( n == 1 ){
            ArrayList<Integer> temp = new ArrayList<Integer>();
            temp.add(0);
            return temp;
        }
        int[] degrees = new int[n];
        ArrayList<Integer>[] graph = new ArrayList[n];
        for(int i = 0; i < n; i++ ){
            graph[i] = new ArrayList<>();
        }
        
        for(int[] edge : edges){
            int a = edge[0];
            int b = edge[1];
            graph[a].add(b);
            graph[b].add(a);
            degrees[a] += 1;
            degrees[b] += 1;
        }
        LinkedList<Integer> bfs = new LinkedList<>();
        boolean[] marked = new boolean[n];
        
        for(int i = 0; i < n; i++ ){
            if( degrees[i] == 1 ){
                bfs.offer(i);
            }
        }
        
        List<Integer> prevLeaves = new ArrayList<>();
        while( !bfs.isEmpty() ){
            int size = bfs.size();
            prevLeaves = new ArrayList<>(bfs);
            while( size > 0 ){
                size -= 1;
                int cur = bfs.poll();
                marked[cur] = true;
                for( int next  : graph[cur] ){
                    if( marked[next] ){
                        continue;
                    }
                    degrees[next] -= 1;
                    if( degrees[next] == 1){
                        bfs.offer(next);
                    }
                }
            }            
        }
        return prevLeaves;
    }
}
​
```

上面的答案在2023年被证实有缺陷。因为没有考虑 indegrees == 1 的节点。

```java
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer>[] adjList = new ArrayList[n];
        int[] indegrees = new int[n];
        for (int i = 0; i < n; i++) {
            adjList[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adjList[edge[0]].add(edge[1]);
            adjList[edge[1]].add(edge[0]);
            indegrees[edge[0]]++;
            indegrees[edge[1]]++;
        }
        List<Integer> ans = new ArrayList<>();
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (indegrees[i] == 1) {
                queue.offer(i);
            }
            if (indegrees[i] == 0) {
                ans.add(i);
            }
        }
        ArrayList<Integer> prevLevel = new ArrayList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            prevLevel = new ArrayList<>(queue);
            while (size > 0) {
                int cur = queue.poll();
                for (int next : adjList[cur]) {
                    indegrees[next]--;
                    if (indegrees[next] == 1) {
                        queue.offer(next);
                    }
                }
                size--;
            }
        }
        ans.addAll(prevLevel);
        return ans;
    }
}
```
