Algorithm
Problem Name: 979. Distribute Coins in Binary Tree
You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.
In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.
Return the minimum number of moves required to make every node have exactly one coin.
Example 1:
Input: root = [3,0,0] Output: 2 Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.
Example 2:
Input: root = [0,3,0] Output: 3 Explanation: From the left child of the root, we move two coins to the root [taking two moves]. Then, we move one coin from the root of the tree to the right child.
Constraints:
- The number of nodes in the tree is
n. 1 <= n <= 1000 <= Node.val <= n- The sum of all
Node.valisn.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
int ans;
public int distributeCoins(TreeNode root) {
ans = 0;
dfs(root);
return ans;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int l = dfs(root.left);
int r = dfs(root.right);
ans += Math.abs(l) + Math.abs(r);
return root.val + l + r - 1;
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const distributeCoins = function(root) {
let res = 0
helper(root)
return res
function helper(node) {
if(node == null) return 0
const left = helper(node.left)
const right = helper(node.right)
res += Math.abs(left) + Math.abs(right)
return node.val + left + right - 1
}
};
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def distributeCoins(self, root):
self.ans = 0
def dfs(node):
if not node: return 0
L, R = dfs(node.left), dfs(node.right)
self.ans += abs(L) + abs(R)
return node.val + L + R - 1
dfs(root)
return self.ans
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0979_DistributeCoinsInBinaryTree
{
private int result = 0;
public int DistributeCoins(TreeNode root)
{
result = 0;
DistributeCoinsCore(root);
return result;
}
public int DistributeCoinsCore(TreeNode node)
{
if (node == null) return 0;
var left = DistributeCoinsCore(node.left);
var right = DistributeCoinsCore(node.right);
result += Math.Abs(left) + Math.Abs(right);
return left + right + node.val - 1;
}
}
}
Input
Output