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.
1var minTime = function(n, edges, hasApple) {
2 const adj = Array.from({ length: n }, () => []);
3 for (const [u, v] of edges) {
4 adj[u].push(v);
5 adj[v].push(u);
6 }
7 return dfs(0, -1, adj, hasApple);
8};
9
10function dfs(node, parent, adj, hasApple) {
11 let total_time = 0;
12 for (const child of adj[node]) {
13 if (child === parent) continue;
14 const child_time = dfs(child, node, adj, hasApple);
15 if (child_time > 0 || hasApple[child]) {
16 total_time += child_time + 2;
17 }
18 }
19 return total_time;
20}The JavaScript solution follows similar logic, utilizing DFS and adjacency lists. Each child is traversed recursively, contributing to the total time when apples are present there.
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.
Typically, BFS is not used here due to path discoveries being depth-centric.