# code tpl

1443. Minimum Time to Collect All Apples in a Tree

{%hackmd theme-dark %}
n = 7,
edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]

start from node 0

1. 0-1, 1-0, count 2

2. find min cost to collect all apples

3. root = 0

0
/ \
1* 2
/ \
4* 5

cost = 4, 0->1, 1->4, 4->1, 1->0 -> count=4

1. build graph tree

2. recursive, return the cost of subtree

for example 4->2, 5->0 , 1->2left+0right+2
0 -> 4(l) + 0(r)

0
/ \
1 2*
/ \ / \
4* 5* 3 6

ans = 8

class Solution(object):
    def minTime(self, n, edges, hasApple):
        """
        :type n: int
        :type edges: List[List[int]]
        :type hasApple: List[bool]
        :rtype: int
        """
        
        tree = defaultdict(list)
        for u, v in edges:
            tree[u].append(v)
            tree[v].append(u)
        
        # 1, 4
        def helper(cur, parent):
            # 4->2, 5->2, 1->2+2+2=6
            # 3->0, 6->0, 2->2
            # 0-> 6+2 = 8
            subTreeCount = 0
            for nxt in tree[cur]:
                if nxt == parent:
                    continue
                subTreeCount += helper(nxt, cur)
                
            if cur == 0:
                # return 8
                return subTreeCount
            
            if hasApple[cur] or subTreeCount > 0:
                
                # not have apple subTreeCount+2
                # I have apple 0+2
                return subTreeCount + 2
            
            return 0
            
        return helper(0, -1)

    # N of number of Nodes
    # TC: O(N)
    # SC: O(N)

###### tags: `mock interview` `面試`