Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you have to spend to collect all apples in the tree, starting at vertex 0 and coming back to this vertex.
The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means that exists an edge connecting the vertices ai and bi. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple; otherwise, it does not have any apple.
Example 1:
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false] Output: 8 Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.
Example 2:
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false] Output: 6 Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.
Example 3:
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false] Output: 0
Constraints:
1 <= n <= 105edges.length == n - 1edges[i].length == 20 <= ai < bi <= n - 1hasApple.length == nThis approach involves using Depth-First Search (DFS) to traverse the tree from the root node (vertex 0). We recursively explore each subtree from the current node. If a subtree contains any apples, we add the cost of traversing to and from that subtree (2 units of time per edge, as we have to go there and come back). This ensures that the solution captures only the necessary paths contributing to the apple collection.
The C solution implements the DFS traversal with a recursive function. An adjacency list represents the graph, and we use it to explore each node's children. We check if a child (subtree) has apples; if so, we add 2 to the total time, accounting for both the forward and return traversal.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of vertices. We explore each vertex once in the DFS traversal.
Space Complexity: O(n), for storing the adjacency list and recursion stack.
Though less intuitive for this problem compared to DFS, a Breadth-First Search (BFS) approach can be implemented to calculate the shortest paths considering leaf nodes. This method explores layers of the tree level by level but is not more efficient in this specific context than DFS, given that we only need to find necessary paths.
This problem inherently suits DFS; BFS would involve using a queue to track nodes but isn't optimal for path-related recursion required here.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) in BFS general terms, still visiting nodes.
Space Complexity: O(n), by the queue usage.
| Approach | Complexity |
|---|---|
| DFS Traversal with Backtracking | Time Complexity: O(n), where n is the number of vertices. We explore each vertex once in the DFS traversal. |
| BFS Alternative Strategy | Time Complexity: O(n) in BFS general terms, still visiting nodes. |
Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python • NeetCodeIO • 22,052 views views
Watch 9 more video solutions →Practice Minimum Time to Collect All Apples in a Tree with our built-in code editor and test cases.
Practice on FleetCode