979.distribute-coins-in-binary-tree.md

979. Distribute Coins in Binary Tree

Breakdowns

Let's simplify the problem to two nodes, suppose we have two nodes A and B, A has 5 coins, B has 0 coin, then A must distribute 4 coins to B, then it requires 4 moves for the 4 coins.

A(5) - B(0)
4 coins ->
= 4 moves

If A has no coins but B has 5 coins, then B must distribute 4 coins to A, then it requires 4 moves for the 4 coins.

A(0) - B(5)
    <- 4 coins = 4 moves

Summary: The number of moves is the se either moving down or up. So the direction doesn't really matter for the result. Moving from A to B is the same as moving from B to A, we just care the balance we need or we can give.

1. How to calculate the number of coins for each node?

We just calculate the balance from left and right subtree, and the balance of the current node is node.val - 1 + left_balance + right_balance.

2. How to calculate the number of moves for each node?

After calculating the balance from subtree, it's the absolute value of the balance. A will send to/receive from abs(4) coins to/from B from above examples, that is the number of moves.

Postorder Traversal

For the root A, we can distribute 1 coin from B, but it's not optimal way, instead, we should distribute from F to A. It's hard to decide how to distribute optimally, because we don't have enough information about the subtree.

             A(0)
        /           \
      B(2)           C(0)
    /     \        /      \
  D(1)    E(0)   F(4)     G(0)

To gain enough information about the subtree, we need to traverse the tree in postorder, we can start distributing from the leaf nodes. For a leaf node, we can directly decide how to distribute coins optimally, becuase the only neighbor a leaf node can reach is its parent.

             A(0)
        /           \             // Bottom-up from leaf nodes
      B(2)           C(0)         ^
  +0/     \-1    +3/      \-1     |
  D(1)    E(0)   F(4)     G(0)    |

// After distributing from leaf nodes
             A(0)
       +0/           \+1
      B(1)           C(2)
    /     \        /      \
  D(1)    E(1)   F(1)     G(1)

// After distributing to root (completed)
             A(1)
        /           \
      B(1)           C(1)
    /     \        /      \
  D(1)    E(1)   F(1)     G(1)

If we represent extra coins as positive number, and needed coins as negative number. Then we can calculate the balance of each node as follows:

balance = node.val - 1 + left_balance + right_balance

        0                 2
(+3) /     \ (-1)  ->  /     \
    4       0         1       1

Each subtree may have too many or too few coins, we just let every child report how much it needs or gives, and move coins along edges to balance the tree. So:

• Leaf nodes: computes balance
• Passes imbalance up to parent
• Parent fixes left and right imbalances via abs(imbalance) moves.

We don't actually care about the direction (to parent or from parent, to child or from child), just the balance from leftand right subtree. - If the balance is positive, the node has extra coins to send to its parent. - If the balance is negative, the node needs coins from its parent. We just care about the absolute number of moves needed to fix left and right subtree. That is bottom-up is all we need.

• The total number of moves is determined by how many net coin imbalance each node neddes to send to or receive from its parent. Because every imbalance → a coin must move along en adge, each node can only interact with it parent and its children, so any surplus or deficit must ba moved along edges.
• 如果直接从金币的角度来考虑，想搞清楚每个金币要移动到哪个节点上，会发现思路非常混乱，很难做。可以换个角度来思考，考虑每条边上的金币“流量”，每条边上的流量就是当前节点需要移动的硬币数。
• 其实重要的就是关注当前树中的三个节点。左子树缺少或剩余了多少金币，右子树缺少或剩余了多少金币，当前树总共缺少或多剩余少金币；子树之间的金币移动统一通过根节点中转并计算，所有多于的金币都收到 root 节点，所有不足的金币都由 root 补足。我们定义一个辅助函数 helper，从这个函数返回就说明该子树已经将金币分配好，而且可以知道它缺少或者剩余多少金币（至于缺少的和多余的怎么处理的不需要知道，你只需要关心给他多少，或者从他那里拿出来多少使该子树金币数平衡即可，你交给该子树的根节点它自会处理），并且返回移动次数。 Source

private var moves = 0
fun distributeCoins(root: TreeNode?): Int {
    dfs(root)
    return moves
}

private fun dfs(root: TreeNode?): Int {
    if (root == null) return 0
    val left = dfs(root.left)
    val right = dfs(root.right)

    // We balance the subtree first, so total moves is the sum of left and right subtree.
    moves += abs(left) + abs(right)

    // Pass up the balance to parent, the move between root and its parent will
    // be calculated in the parent node.
    val balance = root.`val` - 1 + left + right
    return balance
}

There is another easy way to solve this problem: There are n nodes, then it must have n coins, if there are k extra or lack coins, then it requires k moves to distribute to somewhere. And the number of moves is the abs(nodes - coins) for each node:

• Nodes > Coins: Lack coins, we need to move coins from parent to this node.
• Nodes < Coins: Extra coins, we need to move coins from this node to parent.

private var moves = 0
fun distributeCoins(root: TreeNode?): Int {
    dfs(root)
    return moves
}

// Return # of nodes, # of total coins in subtrees
private fun dfs(root: TreeNode?): Pair<Int, Int> {
    if (root == null) return 0 to 0
    val (leftNodes, leftCoins) = dfs(root.left)
    val (rightNodes, rightCoins) = dfs(root.right)

    moves += abs(leftNodes - leftCoins)
    moves += abs(rightNodes - rightCoins)

    return (leftNodes + rightNodes + 1) to (leftCoins + rightCoins + root.`val`)
}