題目

樹是一個無向圖，其中任何兩個頂點只通過一條路徑連線。 換句話說，一個任何沒有簡單環路的連通圖都是一棵樹。

給你一棵包含 n 個節點的數，標記為 0 到 n - 1 。

給定數字 n 和一個有 n - 1 條無向邊的 edges 列表（每一個邊都是一對標籤），

其中 edges[i] = [ai, bi] 表示樹中節點 ai 和 bi 之間存在一條無向邊。

可選擇樹中任何一個節點作為根。當選擇節點 x 作為根節點時，設結果樹的高度為 h 。

在所有可能的樹中，具有最小高度的樹（即，min(h)）被稱為 最小高度樹 。

請你找到所有的 最小高度樹 並按 任意順序 返回它們的根節點標籤列表。

樹的 高度 是指根節點和葉子節點之間最長向下路徑上邊的數量。

示例 1：輸入：n = 4, edges = [[1,0],[1,2],[1,3]] 輸出：[1]

解釋：如圖所示，當根是標籤為 1 的節點時，樹的高度是 1 ，這是唯一的最小高度樹。

示例 2：輸入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] 輸出：[3,4]

示例 3：輸入：n = 1, edges = [] 輸出：[0]

示例 4：輸入：n = 2, edges = [[0,1]] 輸出：[0,1]

提示：1 <= n <= 2 * 104

edges.length == n - 1

0 <= ai, bi < n

ai != bi

所有 (ai, bi) 互不相同

給定的輸入 保證 是一棵樹，並且 不會有重複的邊

解題思路分析

1、廣度優先搜尋；時間複雜度O(n)，空間複雜度O(n)

func findMinHeightTrees(n int, edges [][]int) []int {	if n == 1 {		return []int{0}	}	if n == 2 {		return []int{0, 1}	}	m := make(map[int][]int)	degree := make([]int, n)	for i := 0; i < len(edges); i++ {		a, b := edges[i][0], edges[i][1]		m[a] = append(m[a], b)		m[b] = append(m[b], a)		degree[a]++		degree[b]++	}	queue := make([]int, 0) // 從葉子節點開始遍歷	for i := 0; i < n; i++ {		if degree[i] == 1 {			queue = append(queue, i)		}	}	for n > 2 {		length := len(queue)		n = n - length		for i := 0; i < length; i++ {			node := queue[i]			degree[node] = 0			for j := 0; j < len(m[node]); j++ {				temp := m[node][j]				if degree[temp] > 0 {					degree[temp]--					if degree[temp] == 1 {						queue = append(queue, temp)					}				}			}		}		queue = queue[length:]	}	res := make([]int, 0)	for i := 0; i < len(queue); i++ {		res = append(res, queue[i])	}	return res}

總結

Medium題目，使用暴力法計算每個節點的高度會超時，從葉節點往裡查詢可以一次即可得到結果