A tree rooted at node 0 is given as follows:
- The number of nodes is
nodes
; - The value of the
i
-th node isvalue[i]
; - The parent of the
i
-th node isparent[i]
.
Remove every subtree whose sum of values of nodes is zero.
After doing so, return the number of nodes remaining in the tree.
Example 1:
Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1] Output: 2
Constraints:
1 <= nodes <= 10^4
-10^5 <= value[i] <= 10^5
parent.length == nodes
parent[0] == -1
which indicates that0
is the root.
Solution: Inorder Traversal
For each node, return the sum of all its subtrees and number of nodes including itself after removal.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) { vector<vector<int>> g(nodes); for (int i = 1; i < nodes; ++i) g[parent[i]].push_back(i); // Returns <sum, nodes> of subtree n. function<pair<int,int>(int)> traverse = [&](int n) { int sum = value[n]; int count = 1; for (int x : g[n]) { auto [s, c] = traverse(x); sum += s; count += s ? c : 0; } return make_pair(sum, sum ? count : 0); }; return traverse(0).second; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment