2673. Make Costs of Paths Equal in a Binary Tree Medium

1/**
2 * [2673] Make Costs of Paths Equal in a Binary Tree
3 *
4 * 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.
5 * 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.
6 * Return the minimum number of increments you need to make the cost of paths from the root to each leaf node equal.
7 * Note:
8 * 
9 * 	A perfect binary tree is a tree where each node, except the leaf nodes, has exactly 2 children.
10 * 	The cost of a path is the sum of costs of nodes in the path.
11 * 
12 *  
13 * <strong class="example">Example 1:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2023/04/04/binaryytreeedrawio-4.png" />
15 * Input: n = 7, cost = [1,5,2,2,3,3,1]
16 * Output: 6
17 * Explanation: We can do the following increments:
18 * - Increase the cost of node 4 one time.
19 * - Increase the cost of node 3 three times.
20 * - Increase the cost of node 7 two times.
21 * Each path from the root to a leaf will have a total cost of 9.
22 * The total increments we did is 1 + 3 + 2 = 6.
23 * It can be shown that this is the minimum answer we can achieve.
24 * 
25 * <strong class="example">Example 2:
26 * <img alt="" src="https://assets.leetcode.com/uploads/2023/04/04/binaryytreee2drawio.png" style="width: 205px; height: 151px;" />
27 * Input: n = 3, cost = [5,3,3]
28 * Output: 0
29 * Explanation: The two paths already have equal total costs, so no increments are needed.
30 * 
31 *  
32 * Constraints:
33 * 
34 * 	3 <= n <= 10^5
35 * 	n + 1 is a power of 2
36 * 	cost.length == n
37 * 	1 <= cost[i] <= 10^4
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/make-costs-of-paths-equal-in-a-binary-tree/
43// discuss: https://leetcode.com/problems/make-costs-of-paths-equal-in-a-binary-tree/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn min_increments(n: i32, cost: Vec<i32>) -> i32 {
49        0
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_2673() {
61    }
62}
63