979. Distribute Coins in Binary Tree

T: O(n)
S: O(n) 

硬币的移动规则看似很复杂，因为一个节点可能需要移出硬币，也可能移入硬币，还要求移动次数最少。实际上我们需要观察规律，做一些等价。

如果一个节点的硬币个数是 x，无论是移出还是移入，把该节点的硬币个数变成 1 的最少移动次数必然是 abs(x - 1)。

发现这个规律后，开始二叉树的通用解题思路：假想你现在站在某个根节点上，你如何知道把当前这棵子树的所有节点配平所需的最小移动次数？

那就很简单了，你假想多余的和缺少的硬币都移动到根节点去配平，当然根节点本身也要配平，所以整棵树配平的移动次数就是：

// 让当前这棵树平衡所需的移动次数
Math.abs(left) + Math.abs(right) + (root.val - 1);

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int distributeCoins(TreeNode root) {
        int[] result = new int[1];
        dfs(root, result);
        return result[0];
    }
    private int dfs(TreeNode node, int[] result) {
        if (node == null) {
            return 0;
        }
        int left = dfs(node.left, result);
        int right = dfs(node.right, result);
        // System.out.println(left);
        // System.out.println(right);
        // System.out.println(Math.abs(left) + Math.abs(right) + node.val - 1);
        result[0] += Math.abs(left) + Math.abs(right) + node.val - 1; // move times, so need abs
        return left + right + node.val - 1;
    }
}

/***
ex:
  3 
 0. 
0

left = 0
right = 0
result += (Math.abs(left) + Math.abs(right) + node.val - 1) = 0 + 0 + (0-1) = -1
return -1

-> result[0] = -1;

left = -1
right = 0
result += (Math.abs(left) + Math.abs(right) + node.val - 1) = 1 + 0 + (0-1) = 0
return -2
-> result[0] = -1;

left = 2
right = 0
result += (Math.abs(left) + Math.abs(right) + node.val - 1) = 2 + 0 + (3-1) = 4
return 
 -> result[0] = -1 + 4 = 3;
 so 3 moves



T: O(n)
S: O(n) 


 */

Another easy thought:

class Solution {
    private record NodeInfo(int nodeCount, int coinSum){};
    public int distributeCoins(TreeNode root) {
        int[] result = new int[1];
        dfs(root, result);
        return result[0];
    }
    private NodeInfo dfs(TreeNode node, int[] result) {
        if (node == null) {
            return new NodeInfo(0, 0);
        }
        NodeInfo left = dfs(node.left, result);
        NodeInfo right = dfs(node.right, result);
        result[0] += Math.abs(left.nodeCount - left.coinSum) + Math.abs(right.nodeCount - right.coinSum);

        return new NodeInfo(left.nodeCount + right.nodeCount + 1, left.coinSum + right.coinSum + node.val);
    }
}

/***
idea: total moves = abs(subtree node count - suntree coin sum)

For each node, we record the information 
[# of nodes in the subtree (include itself), # of total coins in the subtree (include itself)]. 

Then we know that for a certain node, 
if there are more coins than nodes in the subtree, the node must "contribute" the redundant coins to its parent. 
Else, if there are more nodes than coins in the subtree, then the node must "take" some coins from the parent.

Both of these two operations will create moves in the tree. 
And we just need to add the absolute value of the (# nodes - # coins) to the final result 
because the move can be "contribute" or "take". 

The time complexity is O(n) because we are just traversing the tree.

ex:
  3 
 0. 
0

NodeInfo(1, 0)

result += 1;

NodeInfo(2, 0)

result += 2




T: O(n)
S: O(n) 


 */

Latest

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int distributeCoins(TreeNode root) {
        int[] result = new int[1];
        dfs(root, result);
        return result[0];
    }
    private int dfs(TreeNode node, int[] result) {
        if (node == null) {
            return 0;
        }
        int leftDiff = dfs(node.left, result);
        int rightDiff = dfs(node.right, result);
        int diff = leftDiff + rightDiff + node.val - 1;

        result[0] += Math.abs(diff);

        return diff;
    }
}

/***
T: O(n)
S: O(n)

we can only calculate moves based on the edge (from subtree to parent), with POST order
-> how many moves, moves = left_sub + right_sub + node.val - 1 (1 node count)


2 -> left child has diff -1, -1 +4 -1 = 2 -> 2 moves
  0
 / \ 1 -> means 1 moves
4   0
/ -> so means -1, one move
0. ex: this 0 needs 1 coin ((node.val - 1)) -> and left_sub (0) + right_sub(0) + (node.val - 1) = -1 (like borrow from parent 1 conis!)
so result = Math.abs(-1) = 1;
return this diff = -1 to upper rescursion

then in  4
 /
4
/
0
left_sub (-1) + right_sub(0) + (node.val - 1) = -1 + 0 + 4 - 1 = 2
so means this node will moves 2 to parent (1 coin already move to child (because left_sub is -1))
(result += math.abs(2)), result = 3

 0 
/ \
2 0 -> then here left_sub (0) + right_sub(0) + (node.val - 1) = -1 
(result += math.abs(-1)), result = 4

 0   -> left_sub (2) + right_sub(-1) + (node.val - 1) = 2 - 1 + 0 - 1 = 0 -> so no moves!
/ \
2 -1 


so result = 4 moves

in ths way, we accumulate from buttom to top, so there is no missing moves!
focus on distribute coins from buttom to top by diff(node val, node count and left_sub, right_sub)
 */