LeetCode 1973: Count Nodes Equal to Sum of Descendants Solution

Master LeetCode problem 1973 (Count Nodes Equal to Sum of Descendants), 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.

1973. Count Nodes Equal to Sum of Descendants

Medium

Tree Depth-First Search Binary Tree

Problem Explanation

Explanation:

To solve this problem, we can perform a Depth First Search (DFS) traversal of the binary tree and at each node, calculate the sum of its descendants. If the sum of the node's descendants is equal to the value of the node itself, we increment a count variable.

Algorithm:

Implement a recursive function dfs to perform DFS traversal.
In the dfs function, calculate the sum of the left and right subtrees for each node.
Check if the sum of the left and right subtrees is equal to the value of the current node. If true, increment the count.
Return the total sum of the left and right subtrees plus the value of the current node.

Time Complexity:

The time complexity of this approach is O(N), where N is the number of nodes in the binary tree.

Space Complexity:

The space complexity of this approach is O(H), where H is the height of the binary tree.

: :

Solution Code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    int count = 0;
    
    public int countSum(TreeNode root) {
        dfs(root);
        return count;
    }
    
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int leftSum = dfs(node.left);
        int rightSum = dfs(node.right);
        
        if (leftSum + rightSum == node.val) {
            count++;
        }
        
        return leftSum + rightSum + node.val;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1973 (Count Nodes Equal to Sum of Descendants)?

This page provides optimized solutions for LeetCode problem 1973 (Count Nodes Equal to Sum of Descendants) 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 1973 (Count Nodes Equal to Sum of Descendants)?

The time complexity for LeetCode 1973 (Count Nodes Equal to Sum of Descendants) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1973 on DevExCode?

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

Back to LeetCode Solutions