⚡Flashcard Drill➔
NeetCode #433LC-1443MediumTrees
← Back to All Problems

#433 · #1443 · Minimum Time to Collect All Apples in a Tree(收集树上所有苹果的最少时间)

📌 Problem Statement & Constraints

Given an undirected tree with n nodes rooted at 0, edges, and a boolean array hasApple, return the minimum time in seconds to collect all apples and return to node 0. Each edge takes 1 second to traverse. Constraints: 1 <= n <= 10^5, edges.length == n - 1, hasApple.length == n.

💡 Core Algorithmic Approaches

  1. An edge is traversed twice (down and back) exactly when its subtree contains at least one apple.
  2. So do a post-order DFS returning the time needed for each subtree.
  3. For each child, if its subtree time is non-zero or the child itself has an apple, add sub + 2 to the total.
  4. The answer is the value at the root.

💻 Benchmark Python3 Implementation

class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        from collections import defaultdict
        g = defaultdict(list)
        for a, b in edges:                 # undirected
            g[a].append(b)
            g[b].append(a)

        def dfs(node: int, parent: int) -> int:
            total = 0
            for c in g[node]:
                if c == parent:
                    continue               # do not go back up
                sub = dfs(c, node)
                # traverse this edge only if the subtree needs it
                if sub > 0 or hasApple[c]:
                    total += sub + 2       # down and back
            return total

        return dfs(0, -1)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node and edge is visited once.
💾 Space Complexity
O(n) for the adjacency list plus O(h) for the recursion.

⚠️ Interview Pitfalls & Follow-ups

  • Adding 2 for every edge unconditionally: an edge whose subtree has no apples is never traversed.
  • Checking only hasApple[c]: a deeper apple also requires the edge, so the subtree time must be tested too.
  • Building a directed graph: the tree is undirected, so both directions are needed.
  • Forgetting the parent guard: the DFS would loop forever on an undirected graph.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems