Medium

题目描述

给你一个整数 n，表示一个由节点 1 到 n 组成的完美二叉树的节点数量。树的根节点是节点 1，树中的每个节点 i 都有两个子节点，其中左子节点是 2 * i，右子节点是 2 * i + 1。

树中的每个节点都有一个代价，由给定的长度为 n 的 0 索引整数数组 cost 表示，其中 cost[i] 是节点 i + 1 的代价。你可以对任意节点的代价执行任意次数的增加 1 操作。

返回使从根节点到每个叶子节点的路径代价相等所需的最少增加次数。

注意：

  • 完美二叉树是指除了叶子节点外，每个节点都恰好有 2 个子节点的树。
  • 路径的代价是路径上所有节点代价的总和。

示例 1：

输入：n = 7, cost = [1,5,2,2,3,3,1]
输出：6
解释：我们可以执行以下增加操作：
- 将节点 4 的代价增加 1 次。
- 将节点 3 的代价增加 3 次。
- 将节点 7 的代价增加 2 次。
从根到每个叶子的路径总代价都为 9。
我们总共增加了 1 + 3 + 2 = 6 次。
可以证明这是能达到的最小答案。

示例 2：

输入：n = 3, cost = [5,3,3]
输出：0
解释：两条路径已经具有相等的总代价，因此不需要增加。

约束条件：

  • 3 <= n <= 10^5
  • n + 1 是 2 的幂
  • cost.length == n
  • 1 <= cost[i] <= 10^4

提示：

  • 从根到叶子的最大代价路径不应被修改。
  • 最优方法是增加所有其他路径，使它们的代价等于最大代价路径。

解题思路

这是一个典型的自底向上贪心算法题目。关键观察是：对于每个内部节点，我们需要确保其左右子树到叶子节点的路径代价相等。

核心思路：

  1. 后序遍历：从叶子节点向根节点处理，确保每一层都满足左右子树路径代价相等
  2. 贪心策略：对于每个内部节点，将代价较小的子树增加到与较大子树相等
  3. 最优性证明：只能增加代价而不能减少，所以必须将所有路径调整到最大路径代价

算法步骤：

  1. 使用DFS后序遍历，从最深的内部节点开始处理
  2. 对于每个节点i，计算其左子树(2i)和右子树(2i+1)的最大路径代价
  3. 将较小的子树路径代价增加到较大的，累计增加次数
  4. 返回当前节点的最大路径代价（节点代价 + 子树最大路径代价）

这种方法确保了每个子树内部路径代价相等，最终整棵树的所有叶子路径代价都相等。时间复杂度O(n)，空间复杂度O(1)。

代码实现

class Solution {
public:
    int minIncrements(int n, vector<int>& cost) {
        int result = 0;
        
        // 从最后一个非叶子节点开始，自底向上处理
        for (int i = n / 2; i >= 1; i--) {
            int left = 2 * i - 1;      // 左子节点索引 (0-based)
            int right = 2 * i;         // 右子节点索引 (0-based)
            
            // 计算需要增加的次数，使左右子树路径代价相等
            result += abs(cost[left] - cost[right]);
            
            // 将父节点的代价加上较大的子树代价
            cost[i - 1] += max(cost[left], cost[right]);
        }
        
        return result;
    }
};

class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int:
        result = 0
        
        # 从最后一个非叶子节点开始，自底向上处理
        for i in range(n // 2, 0, -1):
            left = 2 * i - 1      # 左子节点索引 (0-based)
            right = 2 * i         # 右子节点索引 (0-based)
            
            # 计算需要增加的次数，使左右子树路径代价相等
            result += abs(cost[left] - cost[right])
            
            # 将父节点的代价加上较大的子树代价
            cost[i - 1] += max(cost[left], cost[right])
        
        return result

public class Solution {
    public int MinIncrements(int n, int[] cost) {
        int result = 0;
        
        // 从最后一个非叶子节点开始，自底向上处理
        for (int i = n / 2; i >= 1; i--) {
            int left = 2 * i - 1;      // 左子节点索引 (0-based)
            int right = 2 * i;         // 右子节点索引 (0-based)
            
            // 计算需要增加的次数，使左右子树路径代价相等
            result += Math.Abs(cost[left] - cost[right]);
            
            // 将父节点的代价加上较大的子树代价
            cost[i - 1] += Math.Max(cost[left], cost[right]);
        }
        
        return result;
    }
}

/**
 * @param {number} n
 * @param {number[]} cost
 * @return {number}
 */
var minIncrements = function(n, cost) {
    let result = 0;
    
    // 从最后一个非叶子节点开始，自底向上处理
    for (let i = Math.floor(n / 2); i >= 1; i--) {
        const left = 2 * i - 1;      // 左子节点索引 (0-based)
        const right = 2 * i;         // 右子节点索引 (0-based)
        
        // 计算需要增加的次数，使左右子树路径代价相等
        result += Math.abs(cost[left] - cost[right]);
        
        // 将父节点的代价加上较大的子树代价
        cost[i - 1] += Math.max(cost[left], cost[right]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)