LeetCode 1273: Delete Tree Nodes Solution

Master LeetCode problem 1273 (Delete Tree Nodes), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1273. Delete Tree Nodes

Medium

Array Tree Depth-First Search Breadth-First Search

Problem Explanation

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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1273 (Delete Tree Nodes)?

This page provides optimized solutions for LeetCode problem 1273 (Delete Tree Nodes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1273 (Delete Tree Nodes)?

The time complexity for LeetCode 1273 (Delete Tree Nodes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1273 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1273 in Java, C++, or Python.

Back to LeetCode Solutions