917. Distribute Coins in Binary Tree

Given the root of a binary tree with n nodes and exactly n coins distributed among them, in one move you may transfer a single coin between adjacent (parent-child) nodes. Return the minimum number of moves needed to make every node hold exactly one coin. The tree is given as a level-order array.

Input: A level-order array of the tree (coin counts).

Output: Integer — the minimum number of moves.

Examples

Input: [3,0,0]
Output: 2
Explanation: Move two coins from the root to each child.

Input: [0,3,0]
Output: 3
Explanation: Balance coins across the tree.

Input: [1,0,2]
Output: 2
Explanation: Two transfers balance the tree.

Constraints

• 1<=nodes<=100
• 0<=value<=n
• total coins equals n

Asked by