delete-tree-nodes

< Previous 　　　　　　　　　　　　　　　　 Next >

1273. Delete Tree Nodes (Medium)

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

 

Constraints:

• 1 <= nodes <= 10^4
• -10^5 <= value[i] <= 10^5
• parent.length == nodes
• parent[0] == -1 which indicates that 0 is the root.

Related Topics

[Tree] [Depth-First Search] [Breadth-First Search]

Hints

Hint 1

Traverse the tree using depth first search.

Hint 2

Find for every node the sum of values of its sub-tree.

Hint 3

Traverse the tree again from the root and return once you reach a node with zero sum of values in its sub-tree.