Make Costs of Paths Equal in a Binary Tree
You are given an integer n representing the number of nodes in a perfect binary tree consisting of nodes numbered from 1 to n. The root of the tree is node 1, and each node i in the tree has two children where the left child is node 2 * i and the right child is node 2 * i + 1.
Each node in the tree also has a cost represented by a given 0-indexed integer array cost of size n, where cost[i] is the cost of node i + 1. You are allowed to increment the cost of any node by 1 any number of times.
Return the minimum number of increments you need to make the cost of paths from the root to each leaf node equal.
Note:
- A perfect binary tree is a tree where each node, except the leaf nodes, has exactly
2children. - The cost of a path is the sum of costs of nodes in the path.
Example 1
Input
n = 7, cost = [1,5,2,2,3,3,1]Output
6Increasing node 4 once, node 3 three times, and node 7 twice makes every root-to-leaf path have total cost 9, for a minimum total of 6 increments.
Example 2
Input
n = 3, cost = [5,3,3]Output
0The two root-to-leaf paths already have equal total costs, so no increments are needed.
Constraints
- 3 <= n <= 10^5
- n + 1 is a power of 2
- cost.length == n
- 1 <= cost[i] <= 10^4