LeetCode 979: Distribute Coins in Binary Tree Solution

Master LeetCode problem 979 (Distribute Coins in Binary Tree), 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.

979. Distribute Coins in Binary Tree

Medium

Tree Depth-First Search Binary Tree

Problem Explanation

Explanation:

To solve this problem, we can perform a post-order traversal of the binary tree and calculate the excess coins at each node. The excess at a node represents the number of coins that need to be moved in or out of that node to balance it. We can accumulate the total number of moves required as we traverse the tree.

At each node, we calculate the excess coins as node.val - 1. This excess can be "given" to the parent node or "taken" from the parent node.
We recursively calculate the excess at the left and right children of the current node.
The total moves required for the current node is the absolute value of the sum of excess coins at the current node and its children.
Finally, we return the total moves required to balance the entire tree.

Time Complexity: O(n) - We visit each node exactly once during the post-order traversal. Space Complexity: O(n) - The recursion stack can go up to the depth of the binary tree.

Solution Code

class Solution {
    int moves = 0;
    
    public int distributeCoins(TreeNode root) {
        postOrder(root);
        return moves;
    }
    
    private int postOrder(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int left = postOrder(node.left);
        int right = postOrder(node.right);
        
        moves += Math.abs(left) + Math.abs(right);
        
        return node.val + left + right - 1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 979 (Distribute Coins in Binary Tree)?

This page provides optimized solutions for LeetCode problem 979 (Distribute Coins in Binary Tree) 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 979 (Distribute Coins in Binary Tree)?

The time complexity for LeetCode 979 (Distribute Coins in Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 979 on DevExCode?

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

Back to LeetCode Solutions