Description
Given a binary tree with n nodes and n coins (some nodes have multiple, some have none), find minimum moves to balance.
Examples
Input:
root = [3,0,0]Output:
2Explanation:
Move 2 coins from root to children.
Input:
root = [1]Output:
1Explanation:
Edge case with a single-element array.
Input:
root = [0,3,0]Output:
3Explanation:
The left child has 3 coins but needs only 1. It must give 2 coins to its parent (1 move) and the parent must give 1 coin to the right child (1 move). However, since the task requires move coins through the root, it takes 2 moves from left child to root, then 1 move from root to right child, totaling 3 moves.
Constraints
- •
Number of nodes == n - •
Sum of all coins == n