Problem

Distribute Coins in Binary Tree

Approach

  • wrong idea

    Starting from nodes with value 1 and then going to find these closest nodes with value 0. This idea maybe not optimal and couldn’t get the minimal number of moves. (or equivalently nodes with value 0)

    For example of the case [5,0,0,null,null,0,0,3,null,null,0,null,null,null,0], if use the mentioned method and you will get 15 not 13.

  • Better idea

    First of all, we start from all leaves.

      1. If the node's val is more than `1`, let's move `val - 1` to its' father node. 
  2. If less than `1`, move `1 - val` to its' father node. 
  3. If equals `1`, nothing to od.   Then, in this way, for some node we know the value moved from left subtree and right subtree. Add these values with computed value of self, we can move new value to its' father of current node.

Code

class Solution {
    public int[] tryDistributeCoin(TreeNode root){
        if(root == null) return new int[]{0, 0, 0};
        // ans[0]: the number of nodes
        // ans[1]: the number of coins
        // ans[2]: the final answer
        int[] ans = new int[3];
        ans[0] = 1;
        ans[1] = root.val;
        int[] ls = tryDistributeCoin(root.left);
        int[] rs = tryDistributeCoin(root.right);
        ans[0] += ls[0] + rs[0];
        ans[1] += ls[1] + rs[1];
        ans[2] += Math.abs(ans[0] - ans[1]) + ls[2] + rs[2];
        return ans;
    }
    
    public int distributeCoins(TreeNode root) {
        int[] ans = tryDistributeCoin(root);
        return ans[2];
    }
}