1088. Minimum Height Trees — Topological Trim

Given a tree with n nodes labeled 0..n-1 and n-1 undirected edges, when rooted at a node the tree has some height; return all root labels that minimize the height (there are at most two), sorted ascending. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Array — the minimum-height root labels, sorted.

Examples

Input: {"n":6,"edges":[[3,0],[3,1],[3,2],[3,4],[5,4]]}
Output: [3,4]
Explanation: Two centroids minimize height.

Input: {"n":4,"edges":[[1,0],[1,2],[1,3]]}
Output: [1]
Explanation: The center is optimal.

Input: {"n":1,"edges":[]}
Output: [0]
Explanation: Single node.

Constraints

• 1<=n<=2*10^4
• tree

Asked by