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