1273. Delete Tree Nodes π
Description
A tree rooted at node 0 is given as follows:
- The number of nodes is
nodes
; - The value of the
ith
node isvalue[i]
; - The parent of the
ith
node isparent[i]
.
Remove every subtree whose sum of values of nodes is zero.
Return the number of the remaining nodes 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
Example 2:
Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-2] Output: 6
Constraints:
1 <= nodes <= 104
parent.length == nodes
0 <= parent[i] <= nodes - 1
parent[0] == -1
which indicates that0
is the root.value.length == nodes
-105 <= value[i] <= 105
- The given input is guaranteed to represent a valid tree.
Solutions
Solution 1: DFS
First, we convert the tree into a graph $g$, where $g[i]$ represents all the child nodes of node $i$.
Then we design a function $dfs(i)$, which represents the number of nodes and the sum of the weights in the subtree rooted at node $i$. The answer is $dfs(0)[1]$.
In this function, we recursively calculate the number of nodes and the sum of the weights in the subtree rooted at each child node $j$, and then accumulate these values. If the accumulated value is zero, we set the number of nodes in this subtree to zero. Finally, we return the number of nodes and the sum of the weights in the subtree rooted at node $i$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the number of nodes in the tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|