# Leetcode 310 - Min height trees

`Note:`

- What kind of node should be chosen as our
`root`

? - Nodes with
`indegree == 1`

can be seen as leaves. Those are def not what we want. - Why? Image a path from one leaf from another leaf is like
`l1 - a - b - c - l2`

. Here`b`

is the center and`distance(b, l1) < distance(l1, l2)`

,`distance(b, l2) < distance(l1, l2)`

. - If we pick any
`interior node`

, its distance to any`leaf`

node will be shorter than picking a`leaf`

node as the root. - The more
`inside`

a node is, the shorter the path is to our`leaf`

nodes. - Use a
`map`

to store`edges`

. - Use
`queue`

to store current`leaf`

nodes. - Every time we pop out a
`leaf`

and minus`1`

from its adjacent nodes. If its neighbor’s`indegree === 1`

, add them to the`queue`

. - We need a
`res`

var to store the result. In each iteration of`BFS`

, we clear`res`

first, then we add popped nodes into`res`

. - After the last round of iteration, the result will be in
`res`

.

`Question:`

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 | Input: n = 4, edges = [[1,0],[1,2],[1,3]] |

`Code:`

1 | /** |