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.
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
7 vector<vector<int>> adj(n);
8 for (auto& edge : edges) {
9 adj[edge[0]].push_back(edge[1]);
10 adj[edge[1]].push_back(edge[0]);
11 }
12 return dfs(0, -1, adj, hasApple);
13 }
14
15 int dfs(int node, int parent, vector<vector<int>>& adj, vector<bool>& hasApple) {
16 int total_time = 0;
17 for (int child : adj[node]) {
18 if (child == parent) continue;
19 int child_time = dfs(child, node, adj, hasApple);
20 if (child_time > 0 || hasApple[child]) total_time += child_time + 2;
21 }
22 return total_time;
23 }
24};This C++ solution utilizes DFS to traverse the tree, checking for apples in subtrees and updating the total path length accordingly. If a subtree necessitates visiting for apples, the traversal cost to and from that subtree (2 units) is added.
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.
BFS is outlined but non-optimal here compared to DFS given the recursion needed for paths and conditions like apple checks.