LeetCode 1273: Delete Tree Nodes

Explanation

The problem asks us to delete nodes in a tree and return the number of remaining nodes after deletion. We are given the values of the nodes, their parents, and the values of each node. We need to delete nodes that have a sum of values of their subtree equal to 0, including the node itself. After deleting these nodes, we need to return the number of remaining nodes in the tree.

To solve this problem, we can perform a post-order traversal starting from the leaf nodes. We calculate the sum of the subtree rooted at each node and then propagate this information upwards to the parent nodes. If a node's sum is 0, we mark it for deletion and update the count of remaining nodes accordingly.

class Solution {
    public int deleteTreeNodes(int nodes, int[] parent, int[] value) {
        int[] count = new int[nodes];
        int[] sum = new int[nodes];
        
        for (int i = nodes - 1; i > 0; i--) {
            sum[parent[i]] += sum[i] + value[i];
            count[parent[i]] += count[i] + (sum[i] == 0 ? 0 : 1);
        }
        
        return sum[0] == 0 ? count[0] : count[0] + 1;
    }
}