MediumRating 1683

1443. Minimum Time to Collect All Apples in a Tree

hash-tabletreedepth-first-searchbreadth-first-search

解題說明

Minimum Time to Collect All Apples in a Tree

題目描述：給定一棵無向樹（n 個節點，n-1 條邊），根節點為 0。某些節點上有蘋果（hasApple[i] 為 true）。從根節點出發收集所有蘋果後回到根節點，每走一條邊需要 1 秒（來回 2 秒）。求收集所有蘋果的最短時間。

解題思路：使用 DFS 後序遍歷。對每個節點，先遞迴處理所有子節點。如果某個子樹中有蘋果（子樹的 DFS 回傳值 > 0）或子節點本身有蘋果，那麼我們必須走到那個子節點再走回來，需要加 2 秒。

具體而言，DFS 回傳「從當前節點出發，收集子樹中所有蘋果所需的時間」。對每個子節點 child：

遞迴得到子樹時間 childTime
若 childTime > 0 或 hasApple[child]，則需走這條邊，加 childTime + 2

C++ 解法

複雜度分析

時間複雜度：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)，適合迭代式處理。

延伸思考

若不需要回到根節點（單程即可），最短時間是多少？如何修改 DFS？
若每條邊的權重不同（走不同邊花費不同時間），如何調整？
若蘋果可以動態新增或移除，如何高效更新最短時間？

Minimum Time to Collect All Apples in a Tree — CaffeCode