LC.P2673[使二叉树所有路径值相等的最小代价]

发表于2024-02-28|更新于2024-02-28|LeetCode

|字数总计:156|阅读时长:1分钟|阅读量:

方法一：贪心

根节点到每个叶子节点的路径值相等，实际上等价于以任意节点为根节点的子树到该子树的每个叶子节点的路径值相等。

class Solution {
    public int minIncrements(int n, int[] cost) {
        int ans = 0;
        for (int i = n / 2; i > 0; --i) {
            ans += Math.abs(cost[2 * i - 1] - cost[2 * i]); // 使两个子节点的值变成一样
            cost[i - 1] += Math.max(cost[2 * i - 1], cost[2 * i]); // 累加路径和
        }
        return ans;
    }
}