Sponsored
Sponsored
This 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.
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.
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5 public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
6 List<List<Integer>> adj = new ArrayList<>();
7 for (int i = 0; i < n; i++) {
8 adj.add(new ArrayList<>());
9 }
10 for (int[] edge : edges) {
11 adj.get(edge[0]).add(edge[1]);
12 adj.get(edge[1]).add(edge[0]);
13 }
14 return dfs(0, -1, adj, hasApple);
15 }
16
17 private int dfs(int node, int parent, List<List<Integer>> adj, List<Boolean> hasApple) {
18 int total_time = 0;
19 for (int child : adj.get(node)) {
20 if (child == parent) continue;
21 int child_time = dfs(child, node, adj, hasApple);
22 if (child_time > 0 || hasApple.get(child)) {
23 total_time += child_time + 2;
24 }
25 }
26 return total_time;
27 }
28}The Java solution similarly applies DFS to navigate the tree. It checks each child for apples, iterating through adjacency lists. If apples exist along a path, the necessary travel time is added to the total.
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.
Time Complexity: O(n) in BFS general terms, still visiting nodes.
Space Complexity: O(n), by the queue usage.
While BFS brings layer-level reading, DFS outperforms in apple path marking, providing dedicated traversal.