979. Distribute Coins in Binary Tree


Given the root of a binary tree with N nodes, each node in the tree has node.val coins, and there are N coins total.

In one move, we may choose two adjacent nodes and move one coin from one node to another. (The move may be from parent to child, or from child to parent.)

Return the number of moves required to make every node have exactly one coin.

Example 1:

Input: [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: [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. Example 3:

Input: [1,0,2] Output: 2 Example 4:

Input: [1,0,0,null,3] Output: 4


1<= N <= 100 0 <= node.val <= N



  1. 300这个例子:左边节点需要1个,右边节点需要一个,所以就是需要2个,又因为3是根节点,所以确定了就是需要2步。
  2. 030这个例子:首先3这个节点本身需要1个,需要将另外2个推出去,因为不管这两个会推到哪里,其实都是需要2步,同时因为这个子树已经完成平衡,可以确定不需要再将新的coin推进来,所以这两个就是需要推出去的coin,也就是需要的步数,推给了自己的parent。 重复这个过程直到根节点。


    class Solution {
     public int distributeCoinsStep = 0;
     public int distributeCoins(TreeNode root) {
         if(root == null) return 0;
         return distributeCoinsStep;
     public int distributeCoinsHelper(TreeNode root){
         int left = 0,right = 0;
         if(root.left!=null) left = distributeCoinsHelper(root.left);
         if(root.right!=null) right = distributeCoinsHelper(root.right);
         distributeCoinsStep += Math.abs(left) + Math.abs(right);
         return root.val+left+right-1;