Minimum Height Trees

Hard

Given a tree of n nodes labeled from 0 to n-1 with n-1 edges, return the number of nodes that could be the root of a Minimum Height Tree (MHT). A MHT is one where the longest path from root to any leaf is minimized.

Example 1

Input:  n = 4, edges = [[1,0],[1,2],[1,3]]
Output: 1

Example 2

Input:  n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: 2

Constraints

• 1 <= n <= 2*10^4
• edges.length == n - 1
• The graph is a valid tree.