Link to the Problem
Minimum Time to Collect All Apples in a Tree
Thought Process
Whenever you are at a node, say p, you will collect all apples in p’s subtree before returning back to the original root. This will avoid traveling the same path multiple times.
Say, root is where we start, p is a node in the tree and p has two children – child1, child2 – and both of them have an apple each.root -> p -> child1 -> p -> child2 -> p -> root is always going to be better than root -> p -> child1 -> p -> root -> p -> child2 -> p -> root.
Secondly, time required to travel each edge can be assumed to be 2 because it takes 1 unit time to travel each way. At the end, we must go back to the root as the problem statement states, so we can assume time to be 2 and the direction to be one way. In other words, we can also say that the time required to visit each node is 2 units. We start at root, so for the root, time will be 0.
Algorithm
- Because you have the list of edges, construct a better representation – adjacency list – of the tree.
- Start with the root.
- Find the time required to collect apples in the subtree of each child of the node. Repeat this recursively.
- If there is at least one child in the subtree, we have to collect it. So we will also have to add the time required to visit the every node on the path i.e. current node.
- return the total time.
Code
| class Solution { | |
| unordered_map<int, vector<int>> tree; | |
| unordered_map<int, bool> visited; | |
| vector<bool> hasApple; | |
| /** Convert edge list into adjacency list */ | |
| void createTreeStructure(vector<vector<int>>& edges) { | |
| // Adjacency list representation. | |
| for (auto e: edges) { | |
| tree[e[0]].push_back(e[1]); // a --> b | |
| tree[e[1]].push_back(e[0]); // b --> a | |
| } | |
| } | |
| /** Returns time required to collect apples in the subtree of the 'node'. */ | |
| int traverse(int node, int timeToVisitNode) { | |
| if (visited[node]) { // Already visited this node and its subtree. | |
| return 0; // So no need to visit again. | |
| } | |
| visited[node] = true; // Mark visited to avoid repetition. | |
| int subtreeTime = 0; // Time required to collect apples in subtree. | |
| for (auto childNode: tree[node]) { | |
| subtreeTime += traverse(childNode, /* timeToVisitNode= */ 2); | |
| } | |
| // If the subtree has no apples, subtree time will be 0. And | |
| // if the current node also does not have an apple, then we can | |
| // simply avoid traversing the current branch of the tree to save | |
| // the time. In that case, time required for this subtree will be 0. | |
| if (subtreeTime == 0 && hasApple[node] == false) { | |
| return 0; | |
| } | |
| return subtreeTime + timeToVisitNode; | |
| } | |
| public: | |
| int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) { | |
| this->hasApple = hasApple; | |
| createTreeStructure(edges); | |
| // Time to visit any node is 2 except 0. | |
| return traverse(/* startNode= */ 0, /* timeToVisitNode= */ 0); | |
| } | |
| }; |
Is there anything that is still unclear? Let me know in the comments and I can elaborate further.
Don’t forget like & share the post, and subscribe to the blog to get notifications whenever solution to a new problem is added.
Happy Coding!
Similar Problems
Leetcode #543: Diameter of Binary Tree
Leetcode #110: Balanced Binary Tree
