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] = [a`

indicates that there is an undirected edge between the two nodes _{i}, b_{i}]`a`

and _{i}`b`

in the tree, you can choose any node of the tree as the root. When you select a node _{i}`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

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

**Example 1:**

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

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

**Constraints:**

`1 <= n <= 2 * 10`

^{4}`edges.length == n - 1`

`0 <= a`

_{i}, b_{i}< n`a`

_{i}!= b_{i}- All the pairs
`(a`

are distinct._{i}, b_{i}) - The given input is
**guaranteed**to be a tree and there will be**no repeated**edges.

class Solution: def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]: if n <= 2: return [x for x in range(n)] neighbours = {i: [] for i in range(n)} for e1, e2 in edges: neighbours[e1].append(e2) neighbours[e2].append(e1) leaves = [] for neighbour in neighbours: if len(neighbours[neighbour]) == 1: leaves.append(neighbour) min_height = n while min_height > 2: min_height -= len(leaves) tmp = [] for leaf in leaves: for neighbour in neighbours[leaf]: neighbours[neighbour].remove(leaf) if len(neighbours[neighbour]) == 1: tmp.append(neighbour) leaves = tmp return leaves

If you like dEexams.com and would like to contribute, you can write your article here or mail your article to admin@deexams.com . See your article appearing on the dEexams.com main page and help others to learn.