Simple 12-liner Python with explanation, DFS, O(N) time/space
This solution is based on scanning the tree with Depth-First Search and collecting the "cost" - number of edges we need to travel to pick our apples underneath.
This solution is based on scanning the tree with Depth-First Search and collecting the "cost" - number of edges we need to travel to pick our apples underneath.\n\nTo illustrate how it works let\'s consider Example 1:\n![image](https://assets.leetcode.com/users/ilgor/image_1589125958.png)\n\nFirst DFS will go all the way to the leaf nodes (the order below is arbitrary and doesn\'t matter for the algorithm):\n\n**Node 3:** has no cost from the nodes under and no apple => returns **0**\n**Node 6:** has no cost from the nodes under and no apple => returns **0**\n**Node 4:** has no cost from the nodes under but has **apple** => returns **1**\n**Node 5:** has no cost from the nodes under but has **apple** => returns **1**\n\n**Node 2:** cost from the nodes under (**3** and **6**) is **0** but has **apple** => returns **1**\n**Node 1:** cost from the nodes under (**4** and **5**) is **1+1 = 2** and no apple => returns **2+1 = 3**\n\n**Node 0:** cost from the nodes under (**1** and **2**) is **3+1 = 4** and no apple => returns **4+1 = 5**\n\nThe true cost is always 1 less, since vertex 0 has no parent and available to us right away: **5-1 = 4**\n**Time =** 2 * cost = 2*4 = **8**\n\n```\n# IDEA: use DFS with every iteration returning the cost (number of edges) to travel to all the apple nodes beneath:\n#       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;\n#       since travel is back and forth the time is double of cost\n#       O(N) time, O(N) space\n#\n#       Still linear but faster way for low-hanging apple trees would be to iterate over apples and travel back\n#       from each apple to it\'s parents until vertex \'0\' reached and only add to cost if parent is not traveled before\nclass Solution:\n    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n        routes = collections.defaultdict(list) # use dictionary to store all possible routes from every node\n        for u,v in edges:\n            routes[u].append(v)\n            \n        def dfs(node: int) -> int:\n            cost = 0\n            for child in routes[node]:\n                cost += dfs(child)\n            if cost or hasApple[node]:\n                return cost+1\n            return 0\n            \n        res = dfs(0)\n        return 2*(res-1) if res else 0 # -1 to offset +1 from vertex \'0\' travel to which is free\n
['Depth-First Search', 'Python', 'Python3']