1443. Minimum Time to Collect All Apples in a Tree

Medium
Description

給定一棵無向樹，有 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#

DFS 從根出發，只有當子樹中包含蘋果時，才需要走那條邊（來回各一次，花費 2 秒）。

  • 如果某個子樹中沒有蘋果，完全不需要進入該子樹
  • 如果子樹中有蘋果，則必須走進去再走回來，花費 2 秒
  • 從葉子往上累加，每條「有用的」邊貢獻 2 秒

Approaches#

⭐ 1: DFS on Adjacency List#

  • 概念: 建立鄰接表，DFS 遍歷，從子節點回傳收集蘋果所需的時間，若子樹有貢獻則加上當前邊的 2 秒
  • 時間複雜度: O(n)，每個節點訪問一次
  • 空間複雜度: 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 (不建鄰接表，利用邊的順序)#

  • 概念: 由於 edges 中父子關係可能不固定，仍需建圖。但可以用 visited 陣列取代 parent 參數
  • 時間複雜度: O(n)
  • 空間複雜度: 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 累加 — 子樹貢獻往上匯聚，只走有「收益」的路徑
  • 關鍵技巧: 判斷是否需要走某條邊的關鍵：子樹中是否有蘋果（子節點有蘋果或子樹的回傳時間 > 0）