---
# System prepended metadata

title: code tpl
tags: [mock interview, 面試]

---

# 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
```python=

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` `面試`