Topological Sort
LC #310Medium
Minimum Height Trees
Topological Sort
GoogleAmazonProblem
Find all roots that minimize the height of the resulting tree.
graphtopological-sorttree
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