Minimum Height Trees
Medium · topological sort
A village has n houses, numbered 0 to n - 1, joined by n - 1 two-way roads given as pairs in roads. From any house you can reach every other house, and there are no loops, so the roads form a tree.
Pick one house as the centre. Its *reach* is the greatest number of roads you must walk to get from the centre to some other house, taking the shortest route. A single house has a reach of 0.
Return every house whose reach is as small as possible, in increasing order of house number.
Examples
Example 1
Input: n = 4, roads = [[0, 1], [1, 2], [1, 3]]
Output: [1]
From house 1 every house is one road away. From any other house, some house is two or more roads away.
Example 2
Input: n = 4, roads = [[0, 1], [1, 2], [2, 3]]
Output: [1, 2]
Houses 1 and 2 both reach every house within two roads, while houses 0 and 3 need three.
Example 3
Input: n = 1, roads = []
Output: [0]
With one house, it is the only choice.
Constraints
- 1 <= n <= 1000
- len(roads) = n - 1
- Each road is a pair of different house numbers in the range 0 to n - 1, and no road appears twice.
- Every house can be reached from every other house.