Show problems as
Classic problem #310MediumDepth-First SearchBreadth-First SearchGraph TheoryTopological Sort

Minimum Height Trees

Real-world version: Courier Base on the Campus Walkways
Tracked in this browser only
Read Minimum Height Trees on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A campus has n buildings numbered 0 through n - 1, joined by covered walkways. The walkways arrive as a list of pairs: walkways[k] = [a, b] means one walkway directly joins building a and building b. There are n - 1 walkways, every building is reachable from every other along them, and no walkway is listed twice, so the campus forms a tree.

An internal courier is to be based in one building. The reach of building h is the number of walkways on the route from h to the building furthest from it, counting walkways along the single route that joins the two.

Return every building whose reach is as small as possible, listed in ascending order. For a campus shaped like this there is always either one such building or two.

Examples

Example 1

Input
n = 7, walkways = [[0, 3], [1, 3], [2, 3], [3, 4], [4, 5], [4, 6]]
Output
[3, 4]

From building 3 the routes reach buildings 0, 1, 2 and 4 across one walkway and buildings 5 and 6 across two, so its reach is 2. From building 4 the routes reach buildings 3, 5 and 6 across one walkway and buildings 0, 1 and 2 across two, so its reach is also 2. Both are reported, in ascending order.

Example 2

Input
n = 5, walkways = [[0, 1], [1, 2], [2, 3], [3, 4]]
Output
[2]

The campus is a single corridor. From building 2 the furthest buildings are 0 and 4, each two walkways away, so its reach is 2 and it is the only building reported.

Example 3

Input
n = 2, walkways = [[1, 0]]
Output
[0, 1]

Each building is one walkway from the other, so both have reach 1 and both are reported.

Constraints

  • 1 <= n <= 2 * 10^4
  • walkways.length == n - 1
  • walkways[i].length == 2
  • 0 <= walkways[i][j] <= 2 * 10^4 - 1
  • Every walkway entry is a building number, so it is smaller than n.
  • A walkway never joins a building to itself and no pair of buildings is joined twice.
  • The walkways connect all n buildings into a single tree.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_courier_bases(n: int, walkways: list[list[int]]) -> list[int]:
Java
public List<Integer> bestCourierBases(int n, int[][] walkways)

More on the same topics