/310. Minimum Height Trees

310. Minimum Height Trees

Medium
Graphs42.4% acceptance

Given an undirected tree with node count node_count labeled from 0 to node_count - 1, and a list of undirected edges edge_list where edge_list[i] = [u, v] indicates an edge between nodes u and v, return a list of all root node labels that result in minimum possible tree height when the tree is rooted at that node. The height of a rooted tree is defined as the number of edges on the longest downward path from the root to any leaf. Return the answer in any order.

Example 1

Input: node_count=5, edge_list=[[0,1],[1,2],[2,3],[3,4]]

Output: [2]

Explanation: Rooting at node 2 gives height 2, which is minimum.

Example 2

Input: node_count=7, edge_list=[[0,1],[1,2],[1,3],[3,4],[3,5],[5,6]]

Output: [3]

Explanation: Rooting at node 3 gives minimum height.

Constraints

  • 1 <= node_count <= 20000
  • len(edge_list) == node_count - 1
  • 0 <= u, v < node_count for each edge [u, v] in edge_list
  • u != v for each edge [u, v] in edge_list
  • All edges are distinct
  • Input is guaranteed to be a tree (connected, acyclic)
Python (current runtime)

Case 1

Input: node_count=3, edge_list=[[0,1],[1,2]]

Expected: [1]

Case 2

Input: node_count=8, edge_list=[[0,1],[1,2],[1,3],[3,4],[3,5],[5,6],[5,7]]

Expected: [3,5]

Case 3

Input: node_count=2, edge_list=[[0,1]]

Expected: [0,1]

Case 4

Input: node_count=6, edge_list=[[0,1],[1,2],[2,3],[3,4],[4,5]]

Expected: [2,3]