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
- An edge is traversed twice (down and back) exactly when its subtree contains at least one apple.
- So do a post-order DFS returning the time needed for each subtree.
- For each child, if its subtree time is non-zero or the child itself has an apple, add
sub + 2to the total. - 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
parentguard: 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.