Python 3 | Beats 99% | DFS + Post Order | Logically Explained
Intuition -\nUse DFS to traverse the tree starting from vertex 0, for each vertex check if it or its children have apples, if yes add the distance from starting
**Intuition -**\nUse DFS to traverse the tree starting from vertex 0, for each vertex check if it or its children have apples, if yes add the distance from starting vertex to that vertex to total distance, return total distance as the minimum time to collect all apples.\n\n**Step by Step Logic -**\n1. Initialize a variable total_distance to 0\n2. Perform a DFS starting at vertex 0\n3. For each vertex v visited in the DFS:\n\ta. If v has an apple:\n\t\ti. Add the distance from the starting vertex to v to total_distance\n\tb. If v has an apple or its children have apples:\n\t\ti. Add the distance from the starting vertex to v to total_distance\n4. Return total_distance\n\nThis approach has the same time and space complexity, O(n) for both.\n\n```py\nclass Solution:\n    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n        adj = [[] for i in range(n)]\n        \n        for u, v in edges:\n            adj[u].append(v)\n            adj[v].append(u)\n            \n        queue = [0]\n        q = 1 \n        \n        par = [0]*n \n        \n        vis = [0]*n \n        vis[0] = 1 \n\n        while q > 0:\n            s = queue[-1]\n\n            flag = True\n            for z in adj[s]:\n\n                if not vis[z]:\n                    par[z] = s\n                    flag = False\n                    vis[z] = 1 \n                    q += 1 \n                    queue.append(z)\n                    \n            if flag:\n                for z in adj[s]:\n                    if z == par[s]:\n                        continue\n                    if hasApple[z]:\n                        hasApple[s] = True\n                        \n                queue.pop()\n                q -= 1 \n\n        sm = sum(hasApple)-1 \n\n        return max(0, 2*sm)\n\t\t```
['Depth-First Search', 'Python3']