LC 1443 [M] Minimum Time to Collect All Apples in a Tree - ALawliet/algorithms GitHub Wiki
# IDEA: use DFS with every iteration returning the cost (number of edges) to travel to all the apple nodes beneath:
# if it's a leaf with no apple cost is zero, if it's a node that has apples under we increment the cost by 1;
# since travel is back and forth the time is double of cost
# O(N) time, O(N) space
#
# Still linear but faster way for low-hanging apple trees would be to iterate over apples and travel back
# from each apple to it's parents until vertex '0' reached and only add to cost if parent is not traveled before
class Solution:
def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
G = defaultdict(list) # a.k.a. routes/children/neighbors, use dictionary to store all possible routes from every node
for u, v in edges:
# it says "undirected" like trees are but actually has to be transformed to "bidirected" graph with a visited set
G[u].append(v) ; G[v].append(u)
visited = set()
def dfs(node: int) -> int:
if node in visited:
return 0
visited.add(node)
cost = 0
for child in G[node]:
cost += dfs(child)
# we DFS'd so we collected down to the descendants then came back up
if cost or hasApple[node]: # if it has an apple or a descendant has apple, sum those up
return cost + 1
return 0
res = dfs(0)
return 2*(res-1) if res else 0 # 2 for each node down and back up, -1 to offset +1 from vertex '0' travel to which is free