Minimum Height Trees
Medium
Graphs
Grind 75
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 labeled from 0 to n - 1, and an array edges where edges[i] = [ai, bi] indicates that there is an undirected edge between 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 (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.

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