# 1273. Delete Tree Nodes
A tree rooted at node 0 is given as follows:
The number of nodes is nodes; The value of the i-th node is value[i]; The parent of the i-th node is parent[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
# Solution
Approach 1: DFS after reconstructing the tree.
Approach 2: assuming the params are given top down (numbering the nodes from root to leaf in level order), can go through the array without reconstructing the tree.
# Code (Python)
Approach 1:
import collections
class Solution:
def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
if not nodes:
return 0
children = collections.defaultdict(list)
for i, val in enumerate(parent):
children[val].append(i)
root = children.pop(-1)[0]
return self._recurse(root, children, value)[1]
def _recurse(self, node, children, value):
# return (sum, num of undeleted nodes in subtree including self)
total = value[node]
count = 1
for child in children[node]:
child_total, child_count = self._recurse(child, children, value)
total += child_total
count += child_count
if total == 0:
return (0, 0)
return (total, count)
Approach 2:
def deleteTreeNodes(self, n: int, parent: List[int], value: List[int]) -> int:
# Without reconstructing the tree. This assumes the params are given top down (numbering the nodes from root to leaf in level order)
if n == 1:
return 0 if value[0] == 0 else 1
res = [1] * n
for i in range(n - 1, 0, -1):
value[parent[i]] += value[i]
res[parent[i]] += res[i] if value[i] else 0
return res[0]
# Code (C++)
Approach 1:
Approach 2: