Distribute Coins in Binary Tree
You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.
In one move, you may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.
Return the minimum number of moves required to make every node have exactly one coin.
Example 1
3
/ \
0 0Input
root = [3,0,0]Output
2From the root of the tree, we move one coin to its left child and one coin to its right child.
Example 2
0
/ \
3 0Input
root = [0,3,0]Output
3From the left child of the root, we move two coins to the root, then move one coin from the root to the right child.
Constraints
- The number of nodes in the tree is
n. - 1 <= n <= 100
- 0 <= Node.val <= n
- The sum of all
Node.valisn.