2673.使二叉树所有路径值相等的最小代价

链接：2673.使二叉树所有路径值相等的最小代价
难度：Medium
标签：贪心、树、数组、动态规划、二叉树
简介：你的目标是让根到每一个 叶子结点 的路径值相等。请你返回 最少 需要执行增加操作多少次。

题解 1 - python

• 编辑时间：2024-02-28
• 执行用时：233ms
• 内存消耗：45.47MB
• 编程语言：python
• 解法介绍：dfs时记录左右的节点的值，进行遍历和平衡。

class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int:
        ans = 0
        def dfs(node: int) -> int:
            nonlocal ans
            if node * 2 > n: return cost[node - 1]
            l, r = dfs(node * 2), dfs(node * 2 + 1)
            maxn = max(l, r)
            ans += 2 * maxn - l - r
            return maxn + cost[node - 1]
        dfs(1)
        return ans

题解 2 - python

• 编辑时间：2023-05-07
• 执行用时：324ms
• 内存消耗：48.6MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int:
        level = log2(n+1)
        res = 0
        def dfs(root: int, l: int) -> int:
            nonlocal res
            if l == level : return cost[root]
            left = dfs(root * 2 + 1, l + 1)
            right = dfs(root * 2 + 2, l + 1)
            if left == right :return left + cost[root]
            res += abs(left -right)
            return max(left, right ) + cost[root]
        dfs(0, 1)
        return res

题解 3 - rust

• 编辑时间：2023-05-07
• 执行用时：24ms
• 内存消耗：3.4MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn min_increments(n: i32, cost: Vec<i32>) -> i32 {        
        let level = ((n + 1) as f64).log2() as u32;
        let mut res = 0;
        fn dfs(cost: &Vec<i32>, level: u32, res: &mut i32, root: usize, l: u32) -> i32 {
            if l == level {
                cost[root]
            } else {
                let left = dfs(cost, level, res, root * 2 + 1, l + 1);
                let right = dfs(cost, level, res, root * 2 + 2, l + 1);
                if left == right {
                    left + cost[root]
                } else {
                    *res += (right - left).abs();
                    left.max(right) + cost[root]
                }
            }
        }
        dfs(&cost, level, &mut res, 0, 1);
        res
    }
}

题解 4 - cpp

• 编辑时间：2023-05-07
• 执行用时：168ms
• 内存消耗：132MB
• 编程语言：cpp
• 解法介绍：dfs每次统计左右子树的差值。

class Solution {
public:
    int minIncrements(int n, vector<int>& cost) {
        int level = log2(n + 1), res = 0;
        function<int(int, int)> dfs = [&](int root, int l) -> int {
            if (l == level) return cost[root];
            int left = dfs(root * 2 + 1, l + 1), right = dfs(root * 2 + 2, l + 1);
            if (left == right) return left + cost[root];
            res += abs(right - left);
            return max(left, right) + cost[root];
        };
        dfs(0, 1);
        return res;
    }
};