給定一棵無向樹，有 n 個節點（編號 0 到 n-1），根為節點 0。每條邊需花費 1 秒走過。某些節點上有蘋果（由
hasApple陣列標示）。從節點 0 出發，收集所有蘋果後回到節點 0，求最少需要多少秒。
Example:
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false] Output: 8
Intuition
TIP
DFS 從根出發，只有當子樹中包含蘋果時，才需要走那條邊（來回各一次，花費 2 秒）。
- 如果某個子樹中沒有蘋果，完全不需要進入該子樹
- 如果子樹中有蘋果，則必須走進去再走回來，花費 2 秒
- 從葉子往上累加，每條「有用的」邊貢獻 2 秒
Approaches
⭐ 1. DFS on Adjacency List — O(n) / O(n)
- Idea: 建立鄰接表，DFS 遍歷，從子節點回傳收集蘋果所需的時間，若子樹有貢獻則加上當前邊的 2 秒
- Time:
O(n)，每個節點訪問一次 - Space:
O(n)，鄰接表 + 遞迴堆疊
class Solution {
fun minTime(n: Int, edges: Array<IntArray>, hasApple: List<Boolean>): Int {
val adj = Array(n) { mutableListOf<Int>() }
for ((u, v) in edges) {
adj[u].add(v)
adj[v].add(u)
}
fun dfs(node: Int, parent: Int): Int {
var totalTime = 0
for (child in adj[node]) {
if (child == parent) continue
val childTime = dfs(child, node)
// 如果子樹有蘋果或子樹中收集蘋果需要時間，則需要走這條邊
if (childTime > 0 || hasApple[child]) {
totalTime += childTime + 2
}
}
return totalTime
}
return dfs(0, -1)
}
}2. DFS (no adjacency list, use edge order) — O(n) / O(n)
- Idea: 由於 edges 中父子關係可能不固定，仍需建圖。但可以用 visited 陣列取代 parent 參數
- Time:
O(n) - Space:
O(n)
class Solution {
fun minTime(n: Int, edges: Array<IntArray>, hasApple: List<Boolean>): Int {
val adj = Array(n) { mutableListOf<Int>() }
for ((u, v) in edges) {
adj[u].add(v)
adj[v].add(u)
}
val visited = BooleanArray(n)
fun dfs(node: Int): Int {
visited[node] = true
var totalTime = 0
for (child in adj[node]) {
if (visited[child]) continue
val childTime = dfs(child)
if (childTime > 0 || hasApple[child]) {
totalTime += childTime + 2
}
}
return totalTime
}
return dfs(0)
}
}🔑 Takeaways
- Pattern: 樹上 DFS 累加 — 子樹貢獻往上匯聚，只走有「收益」的路徑
- Key trick: 判斷是否需要走某條邊的關鍵：子樹中是否有蘋果（子節點有蘋果或子樹的回傳時間 > 0）