#310

Minimum Height Trees

specialist · 975 · lc medium +32 · verified · 42.4% accepted · 8,888 likes · top 23%

Description

A tree is an undirected connected graph with no simple cycles. Given a tree of n nodes labeled 0 to n - 1 and an array of n - 1 edges where edges[i] = [ai, bi] indicates an undirected edge, any node may serve as root. Choosing root x gives the tree height h. Nodes that minimize h are called minimum height tree (MHT) roots.

Return a list of all MHT root labels 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:

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

Output: [1]

Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

Example 2:

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

Output: [3,4]

Code

1

2

3

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]: