Each node's value is the number of coins currently stored there. The tree has exactly as many coins in total as it has nodes. Return the fewest moves needed to leave exactly one coin at every node.
One move transfers one coin across one edge, either from a parent to a child or from a child to its parent. A coin that crosses several edges requires a separate move for each edge.
Examples use level-order arrays. After the root, each present node contributes left and right child entries in queue order. null marks a missing child, and trailing missing entries may be omitted.
Example 1:
Input: root = [0,0,4,null,null,0]
Output: 4Explanation: The node with 4 coins keeps one and sends one to its own left child. It sends two coins to the root, which keeps one and passes one to its left child. These four edge transfers leave one coin at each node.
Example 2:
Input: root = [1,0,2]
Output: 2Explanation: Move one coin from the right child to the root, then from the root to the left child. Two moves are required.
Example 3:
Input: root = [1,1,1]
Output: 0Explanation: Every node already has one coin, so no moves are necessary.
Constraints:
- The tree has
nnodes, where1 <= n <= 100. 0 <= Node.val <= n- The sum of all node values is exactly
n.