題目描述:
給定一棵無向樹(n 個節點,n-1 條邊),根節點為 0。某些節點上有蘋果(hasApple[i] 為 true)。從根節點出發收集所有蘋果後回到根節點,每走一條邊需要 1 秒(來回 2 秒)。求收集所有蘋果的最短時間。
解題思路: 使用 DFS 後序遍歷。對每個節點,先遞迴處理所有子節點。如果某個子樹中有蘋果(子樹的 DFS 回傳值 > 0)或子節點本身有蘋果,那麼我們必須走到那個子節點再走回來,需要加 2 秒。
具體而言,DFS 回傳「從當前節點出發,收集子樹中所有蘋果所需的時間」。對每個子節點 child:
時間複雜度:O(n) — DFS 遍歷每個節點一次。
空間複雜度:O(n) — 鄰接表 O(n) 加上遞迴堆疊深度最壞 O(n)。
1. Build adjacency list from edges
2. DFS(node, parent):
a. total = 0
b. For each child in adj[node] (skip parent):
- childTime = DFS(child, node)
- If childTime > 0 or hasApple[child]:
total += childTime + 2
c. Return total
3. Return DFS(0, -1)BFS + 自底向上標記:先 BFS 得到每層的節點,然後從葉節點向上標記「路徑上有蘋果」。每條被標記的邊貢獻 2 秒。時間 O(n),但實作較繁瑣。
拓撲排序(葉到根):計算每個節點的入度,從葉節點開始逐層往上處理。若葉節點有蘋果,標記其父邊。時間 O(n),適合迭代式處理。