🔥Python3🔥 DFS (Explained)
Code with no comments at the end, in case you don\'t want to read the story but just want to compare mine with yours\n\nIntuition\n- One way or another we will 
**Code with no comments at the end, in case you don\'t want to read the story but just want to compare mine with yours**\n\n**Intuition**\n- One way or another we will have to construct the tree first, since the tree is undriected, we just add both directions. I\'m using a hashmap to represent the tree, where key represents a starting node, and value is a list representing the neighbor nodes of the key node.\n - The difference between tree and graph is that tree doesn\'t contain any cycles in it, however since this tree is undirected, a node\'s neighbor nodes will also contain its parent node (I just called it one edge cycle) e.g., node A connected to node B means B is also connected to A. (We need to check this one edge cycle when doing the search)\n - In order to pick up an apple on some node, we will have to travel from the root to that node with the shorest path. Since this is a tree, the shorest path is just going from the root to the node that has an apple (Again, we should\'t travel back and forth, which means we shouldn\'t visit parent node if we come from there).\n - We start from node 0 and using a postorder DFS to search the tree.\n - Once we visited all the children nodes, we need to check two things:\n \t- Are there any apple in the children nodes?\n \t- Is the current node has an apple?\n - If any of these two conditions is True, we will have to come to this node in our result, so just add 2 (Adding 2, because 1 for coming to this node, 1 for going back.)\n\n**TC: O(N)**\n\n**Code with comments**\n```python\nclass Solution:\n    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n        # Construct the tree using the edges.\n        # Since the tree is undricted, we need to add both directions in the tree.\n        tree = defaultdict(list)\n        for s,e in edges:\n            tree[s].append(e)\n            tree[e].append(s)\n        \n        # node is the current node we are examing.\n        # par is the node\'s direct parent node.\n        def dfs(node,par):\n            res = 0\n            # Since it is a tree, there will be no cycles.\n            # However, the tree is undirected, which means one of the neighbor node is its parent node.\n            for nei in tree[node]:\n                # Make sure we are not going backward to its parent node.\n                if nei != par:\n                    res += dfs(nei,node)\n            \n            # case1, res != 0, this means we have found some apples down the tree\n            # case2, hasApple[node]==True, this means the current node has a apple on it\n            # In both cases, we will have to increase the result by 2.\n            # Adding 2 because we need 1 to get to this node and 1 going back\n            if res or hasApple[node]:\n                return res + 2\n            \n            # There is no apple on this node or down the tree, res should 0.\n            # In this case we don\'t want to come to this node at all, so return 0.\n            return res\n        \n        # Following the dfs, you can see that when we coming back to node 0, if there are some apples in the tree,\n        # We added an extra 2 to the result, so we need to -2 here.\n        # In case there is no apples in this tree, dfs will return 0, but we can\'t return -2, so just return 0\n        return max(dfs(0,-1)-2, 0)\n```\n\n**Code without comments**\n```python\nclass Solution:\n    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n\n        tree = defaultdict(list)\n        for s,e in edges:\n            tree[s].append(e)\n            tree[e].append(s)\n        \n        def dfs(node,par):\n            \n            res = 0\n            for nei in tree[node]:\n                if nei != par:\n                    res += dfs(nei,node)\n            \n            if res or hasApple[node]:\n                return res + 2\n\n            return res\n\n        return max(dfs(0,-1)-2, 0)\n```\n\n**Upvote** if you like this post.\n\n**Connect with me on [LinkedIn](https://www.linkedin.com/in/meida-chen-938a265b/)** if you\'d like to discuss other related topics\n\n\uD83C\uDF1F If you are interested in **Machine Learning** || **Deep Learning** || **Computer Vision** || **Computer Graphics** related projects and topics, check out my **[YouTube Channel](https://www.youtube.com/@meidachen8489)**! Subscribe for regular updates and be part of our growing community.\n\n
[]