You’re given the root of a binary tree with n nodes and a total of n coins. Each node node.val is the number of coins at that node. In one move, you may move one coin between two adjacent nodes (parent ↔ child).
Return the minimum number of moves to make every node have exactly one coin.
Key idea (postorder flow):
Let balance(node) = coins that must flow out of this node to its parent (positive = surplus to send up, negative = deficit to receive) after balancing its children.
For each node:
Get L = balance(left), R = balance(right).
Moves added here = |L| + |R| (each coin unit flowing across an edge costs 1 move).
Node’s balance to parent = node.val + L + R - 1.
Sum moves across all nodes.
Input: root = [3,0,0]
Output: 2
Explanation:
Move 1 coin from root→left, and 1 coin from root→right.
Input: root = [0,3,0]
Output: 3
Explanation:
Move two coins left→root (2 moves), then one coin root→right (1 move).
Input: root = [1,0,2]
Output: 2
Explanation:
One coin from right child→root (1), then root→left (1).
Accepted:
Submission: