268. Minimum Height Trees
You are given a tree: a connected, undirected graph with n nodes labeled 0 to n − 1 and no cycles. It is described by an integer n and a list edges of n − 1 pairs, where edges[i] = [a, b] means nodes a and b are joined by an edge.
Any node can be picked as the root, and rooting the tree gives it a height: the number of edges on the longest path from that root down to a leaf. Some roots keep the tree shallow; others stretch it out.
Return the labels of every node that achieves the minimum possible height when used as the root, sorted in increasing order. A tree always has either one or two such nodes.
Example 1:
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3, 4]
Explanation: Rooted at 3 or at 4 the tree has height 2. Every other root gives height 3 or more, so the answer is [3, 4].
Example 2:
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: Node 1 touches all three other nodes, so rooting there gives height 1. Rooting at 0, 2, or 3 gives height 2.
Constraints:
- 1 ≤ n ≤ 2 * 10⁴
- edges.length == n - 1
- 0 ≤ a, b < n and a ≠ b
- The input is guaranteed to be a valid tree (connected, acyclic).
- Report the answer labels in increasing order.
Hints:
You could root the tree at every node and BFS to measure each height, but that is O(n²). Think about *where* the best roots must sit: they are the middle of the tree's longest path.
Peel the tree like an onion: repeatedly remove all current leaves (degree-1 nodes) at once. The last one or two nodes left standing are the centroids — exactly the minimum-height roots.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Expected output: [3, 4]