#2673
Make Costs of Paths Equal in a Binary Tree
specialist · 740 · lc medium +31 · verified · 58.3% accepted · 664 likes · top 54%
Description
A perfect binary tree has n nodes numbered 1 to n with root 1, left child 2*i, and right child 2*i + 1. Each node i has cost cost[i-1]. You may increment any node's cost by 1 any number of times. Return the minimum total increments so every root-to-leaf path has the same total cost.
Example 1:
Input: n = 7, cost = [1,5,2,2,3,3,1]
Output: 6
Explanation: We can do the following increments:
- Increase the cost of node 4 one time.
- Increase the cost of node 3 three times.
- Increase the cost of node 7 two times.
Each path from the root to a leaf will have a total cost of 9.
The total increments we did is 1 + 3 + 2 = 6.
It can be shown that this is the minimum answer we can achieve.
Example 2:
Input: n = 3, cost = [5,3,3]
Output: 0
Explanation: The two paths already have equal total costs, so no increments are needed.
Code
1
2
3