Python O(n) by DFS [w/ Visualization]
Python O(n) by DFS\n\n---\n\nVisualization:\n\n\n---\n\nImplementation by DFS\n\n\nfrom collections import defaultdict\n\nclass Solution:\n    def minTime(self,
Python O(n) by DFS\n\n---\n\n**Visualization**:\n![image](https://assets.leetcode.com/users/images/13a90a44-766e-422e-9312-af0df84c5d78_1596517473.357243.png)\n\n---\n\n**Implementation** by DFS\n\n```\nfrom collections import defaultdict\n\nclass Solution:\n    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n        \n        adjacency_list = defaultdict(list)\n        \n        # Build adjacency list to represent the tree\n        for src_node, dst_node in edges:\n            adjacency_list[src_node].append(dst_node)\n            adjacency_list[dst_node].append(src_node)\n        \n        # Record of visited nodes\n        visited = set()\n        \n        #------------------------------------------------------------------------------------\n        def collect_in_dfs(cur_node):\n            \n            visited.add(cur_node)\n            \n            cost_of_collect = 0\n            \n            for child_node in adjacency_list[cur_node]:\n                \n                if child_node in visited:\n                    # avoid repeated traversal\n                    continue\n                \n                \n                cost_from_child = collect_in_dfs(child_node)\n                \n                if cost_from_child or hasApple[child_node]:\n                    # update cost of collection (i.e., cost of green arrows)\n                    # The first +1 is for path from cur_node to child_node, and the second +1 is for going back.\n\t\t\t\t\t# Totally, +2\n\n                    cost_of_collect += cost_from_child + 2\n            \n            return cost_of_collect\n        \n        #------------------------------------------------------------------------------------\n        root_node_idx = 0\n        return collect_in_dfs(cur_node=root_node_idx)\n        \n        \n```\n\n---\n\nReference:\n\n[1] [USFCA: DFS visualization and demo animation](https://www.cs.usfca.edu/~galles/visualization/DFS.html)\n\n[2] [Python official docs about defaultdict](https://docs.python.org/3/library/collections.html#collections.defaultdict)
['Depth-First Search', 'Recursion', 'Python', 'Python3']