1202. Distribute Coins in Binary Tree

Given a binary tree (level-order with null for missing nodes) where the total number of coins equals the number of nodes, in one move you may transfer a coin between adjacent nodes (parent and child). Return the minimum number of moves so every node holds exactly one coin. The input is JSON {tree}.

Input: JSON {tree}.

Output: Integer — the minimum number of moves.

Examples

Input: {"tree":[3,0,0]}
Output: 2
Explanation: Move a coin to each child.

Input: {"tree":[0,3,0]}
Output: 3
Explanation: Move coins across the tree.

Input: {"tree":[1,0,2]}
Output: 2
Explanation: Balance the coins.

Constraints

• 1<=nodes<=100

Asked by