題目

給你一棵有 n 個節點的無向樹，節點編號為 0 到 n-1 ，它們中有一些節點有蘋果。

透過樹上的一條邊，需要花費 1 秒鐘。

你從節點0出發，請你返回最少需要多少秒，可以收集到所有蘋果，並回到節點 0 。

無向樹的邊由 edges 給出，其中 edges[i] = [fromi, toi] ，表示有一條邊連線 from 和 toi 。

除此以外，還有一個布林陣列 hasApple ，其中 hasApple[i] = true 代表節點 i 有一個蘋果，

否則，節點 i 沒有蘋果。

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

hasApple = [false,false,true,false,true,true,false] 輸出：8

解釋：上圖展示了給定的樹，其中紅色節點表示有蘋果。一個能收集到所有蘋果的最優方案由綠色箭頭表示。

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

hasApple = [false,false,true,false,false,true,false] 輸出：6

解釋：上圖展示了給定的樹，其中紅色節點表示有蘋果。一個能收集到所有蘋果的最優方案由綠色箭頭表示。

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

hasApple = [false,false,false,false,false,false,false] 輸出：0

提示：1 <= n <= 10^5

edges.length == n-1

edges[i].length == 2

0 <= fromi, toi <= n-1

fromi < toi

hasApple.length == n

解題思路分析

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

func minTime(n int, edges [][]int, hasApple []bool) int {	arr := make([][]int, n)	for i := 0; i < len(edges); i++ {		a, b := edges[i][0], edges[i][1]		arr[a] = append(arr[a], b)		arr[b] = append(arr[b], a)	}	visited := make([]bool, n)	res, _ := dfs(arr, hasApple, visited, 0)	if res >= 2 {		return res - 2 // 遍歷N個點，長度：2N-2	}	return 0}func dfs(arr [][]int, hasApple, visited []bool, index int) (int, bool) {	visited[index] = true	res := 0	has := false	if hasApple[index] == true {		has = true	}	for i := 0; i < len(arr[index]); i++ {		next := arr[index][i]		if visited[next] == true {			continue		}		total, isExist := dfs(arr, hasApple, visited, next)		if isExist {			has = true			res = res + total		}	}	if has == true {		return res + 2, true	}	return 0, false}

2、遍歷；時間複雜度O(n)，空間複雜度O(n)

func minTime(n int, edges [][]int, hasApple []bool) int {	ans := 0	m := make([]bool, n)	m[0] = true	for i := 0; i < len(edges); i++ {		from, to := edges[i][0], edges[i][1]		if m[from] {			m[to] = true		} else {			m[from] = true			// 改變資料			// [[0 2] [0 3] [1 2]] => [[0 2] [0 3] [2 1]]			edges[i][0], edges[i][1] = edges[i][1], edges[i][0]		}	}	for i := len(edges) - 1; i >= 0; i-- {		from, to := edges[i][0], edges[i][1]		if hasApple[to] {			hasApple[from] = true			ans += 2		}	}	return ans}

總結

Medium題目，可以採用深度優先搜尋從0開始遍歷