Dashboard
LC #310

Minimum Height Trees

Pattern · ?GoogleAmazon

Problem

Find all roots that minimize the height of the resulting tree.

Constraints

  • 1 ≤ n ≤ 2 × 10⁴
  • 0 ≤ edges.length ≤ n − 1
  • edges[i].length == 2, 0 ≤ aᵢ, bᵢ < n
  • Connected undirected tree (no cycles)

Example

Input
n = 4, edges = [[1,0],[1,2],[1,3]]
Output
[1]
Why
Node 1 is center. As root, tree height = 1. Any other root gives height 2

Spot the pattern

Which pattern cracks it?

Hints

One at a time
Solve on LeetCode ↗