176. Minimum Height Trees

Medium · Graph

A tree is an undirected, connected, acyclic graph with n nodes labelled 0 to n-1. Any node can be chosen as the root; different roots give trees of different heights. A minimum-height tree is one whose height is as small as possible.

The input is [n, edges], where edges is a list of [u, v] pairs. Return the list of all root labels that produce a minimum-height tree, sorted in ascending order (there are always one or two such roots).

Examples

Example 1
Input: [4,[[1,0],[1,2],[1,3]]]
Output: [1]
Explanation: Rooting at node 1 gives height 1 — the minimum.
Example 2
Input: [6,[[3,0],[3,1],[3,2],[3,4],[5,4]]]
Output: [3,4]
Explanation: Rooting at 3 or 4 both give the minimum height.

Constraints