Medium

Distribute Coins in Binary Tree

LAB

Given a binary tree encoded as level-order with -100000 as null, return the minimum coin moves so every node has one coin.

EXAMPLES

Example 1

Input
{
  "root": [
    3,
    0,
    0
  ]
}

Output
2

FUNCTION SHAPE

root: intArray→int

SOLUTION NOTE

Key insight: we reason about EDGES, not nodes. For each edge, we compute exactly how many coins must flow across it: |subtree_size - subtree_coin_sum|. We don't care where coins come from!

Reveal reference solution +

pythonREFERENCE

def distributeCoins(self, root: Optional[TreeNode]) -> int:
    res = 0

    def size_sum(root):
        if not root: return 0, 0
        left_size, left_sum = size_sum(root.left)
        right_size, right_sum = size_sum(root.right)
        nonlocal res

        # Coins that must flow across this edge = |size - sum|
        res += abs(left_size - left_sum) + abs(right_size - right_sum)

        return (left_size + 1 + right_size,
                left_sum + root.val + right_sum)

    size_sum(root)
    return res

TimeO(n)

SpaceO(h)

Open on LeetCode ↗