491. Spread the Coins
A festival organiser has set up booths in a binary tree layout whose entrance booth is root. The booth with value val currently holds that many coins, and the total number of coins over all booths is exactly equal to the number of booths. In one step a helper may carry a single coin from a booth to a booth that is directly connected to it, meaning its parent or one of its children.
Return the minimum number of steps needed so that every booth ends up holding exactly one coin. Coins may be passed along through intermediate booths. Think of each step as one coin crossing one connection of the tree.
Example 1
- Input:
- root = [0,3,0,null,null,1,1]
- Output:
- 3
- Explanation:
The left child sends its two spare coins up (2 moves), the root keeps one and passes the other to its right child (1 move), for 3 moves.
Example 2
- Input:
- root = [1,0,3,0,null,0,2]
- Output:
- 7
- Explanation:
Counting the net coins that must cross each connection (1 + 2 + 1 + 1 + 2) gives 7 moves.
Constraints
1 ≤ number of nodes n ≤ 104
0 ≤ Node.val ≤ n
The sum of all Node.val equals n.
The answer always fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)