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

# 0310. Minimum Height Trees

<https://leetcode.com/problems/minimum-height-trees>

## Description

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.

**Example 1:**

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

```
**Input:** n = 4, edges = [[1,0],[1,2],[1,3]]
**Output:** [1]
**Explanation:** As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.
```

**Example 2:**

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

```
**Input:** n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
**Output:** [3,4]
```

**Example 3:**

```
**Input:** n = 1, edges = []
**Output:** [0]
```

**Example 4:**

```
**Input:** n = 2, edges = [[0,1]]
**Output:** [0,1]
```

**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.

## ac

<https://leetcode.com/problems/minimum-height-trees/discuss/76055/Share-some-thoughts>

```java
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<Integer>();
        // edge cases
        if (n == 1) {
            res.add(0);
            return res;
        }

        // build graph, degree
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        int[] degree = new int[n];
        for (int[] e : edges) {
            if (!graph.containsKey(e[0])) graph.put(e[0], new HashSet<>());
            if (!graph.containsKey(e[1])) graph.put(e[1], new HashSet<>());
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
            degree[e[0]]++;
            degree[e[1]]++;
        }

        // BFS
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < degree.length; i++) {
            if (degree[i] == 1) q.offer(i);
        }
        while (!q.isEmpty() && n > 2) {
            int len = q.size();  // layer by layer
            for (int i = 0; i < len; i++) {
                int curr = q.poll();
                n--;
                int parent = graph.get(curr).iterator().next();  // leaf's parent
                degree[parent]--;
                if (degree[parent] == 1) q.offer(parent);  // add new leaf
            }
        }

        // add remaining to result
        res.addAll(q);

        return res;
    }
}

/*
build graph
build degree
queue BFS
*/

/* Cleaner version */
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    if (n == 1) return Collections.singletonList(0);

    List<Set<Integer>> adj = new ArrayList<>(n);
    for (int i = 0; i < n; ++i) adj.add(new HashSet<>());
    for (int[] edge : edges) {
        adj.get(edge[0]).add(edge[1]);
        adj.get(edge[1]).add(edge[0]);
    }

    List<Integer> leaves = new ArrayList<>();
    for (int i = 0; i < n; ++i)
        if (adj.get(i).size() == 1) leaves.add(i);

    while (n > 2) {
        n -= leaves.size();
        List<Integer> newLeaves = new ArrayList<>();
        for (int i : leaves) {
            int j = adj.get(i).iterator().next();
            adj.get(j).remove(i);
            if (adj.get(j).size() == 1) newLeaves.add(j);
        }
        leaves = newLeaves;
    }
    return leaves;
}
```