Description
A tree of n nodes, find all nodes that when chosen as root minimize the tree height. Use topological sorting from leaves inward.
Examples
Input:
n = 4, edges = [[1,0],[1,2],[1,3]]Output:
[1]Explanation:
Node 1 as root gives minimum height of 1.
Input:
n = 1, edges = []Output:
[0]Explanation:
With only one node, that node must be the root and gives a tree height of 0, which is the minimum possible.
Input:
n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]]Output:
[3]Explanation:
This is a linear tree (path graph). The optimal root is the middle node 3, which minimizes the maximum distance to any leaf. Node 3 as root gives height 3 (distance to nodes 0 or 6), while any other root would give height 4 or more.
Constraints
- •
1 ≤ n ≤ 2 * 10⁴ - •
edges.length == n - 1