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 the node 2 * i and the right child is 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:
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.
Constraints:
3 <= n <= 105n + 1 is a power of 2cost.length == n1 <= cost[i] <= 104This approach involves recursively calculating the cost of each path from the root to the leaf and ensuring all paths have the same cost by incrementing node costs where necessary.
We create an array to store the cumulative path costs from each node to the leaves. Starting from the last node, we calculate the path cost by checking the costs from its child nodes. This ensures we have path costs for all root to leaf paths. The maximum path cost is then used to calculate the number of increments needed to make all paths equal.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) as each node is processed once.
Space Complexity: O(n) to store path costs.
This approach uses an iterative level-order traversal of the binary tree, utilizing a queue to manage nodes, while keeping track of path costs level-by-level.
This implementation iteratively calculates the maximum path costs using a straightforward loop. We gather costs up the tree while modifying increment counts through a greedy approach, which ensures each node's child paths are maximized efficiently.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) as each node is checked once.
Space Complexity: O(n) for path cost storage.
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n) as each node is processed once. |
| Iterative Approach with Queue | Time Complexity: O(n) as each node is checked once. |
Diameter of Binary Tree - Leetcode 543 - Python • NeetCodeIO • 68,435 views views
Watch 9 more video solutions →Practice Make Costs of Paths Equal in a Binary Tree with our built-in code editor and test cases.
Practice on FleetCode