Minimum Height Trees
Problem
A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.
Given a tree of
n
nodes labelled from0
ton - 1
, and an array ofn - 1
edges
whereedges[i] = [ai, bi]
indicates that there is an undirected edge between the two nodesai
andbi
in the tree, you can choose any node of the tree as the root. When you select a nodex
as the root, the result tree has heighth
. Among all possible rooted trees, those with minimum height (i.e.min(h)
) are called minimum height trees (MHTs).Return a list of all MHTs' root labels. You can return the answer in any order.
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
Example 1:
Example 2:
Pseudocode
Solution
Time and Space Complexity
Time
What did the code do
Total -
Space
What did the code do
Total -
Last updated