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

难度: Medium

给你一个整数 n 表示一棵 满二叉树 里面节点的数目，节点编号从 1 到 n 。根节点编号为 1 ，树中每个非叶子节点 i 都有两个孩子，分别是左孩子 2 * i 和右孩子 2 * i + 1 。

树中每个节点都有一个值，用下标从 0 开始、长度为 n 的整数数组 cost 表示，其中 cost[i] 是第 i + 1 个节点的值。每次操作，你可以将树中任意节点的值增加 1 。你可以执行操作任意次。

你的目标是让根到每一个 叶子结点 的路径值相等。请你返回最少需要执行增加操作多少次。

注意：

满二叉树 指的是一棵树，它满足树中除了叶子节点外每个节点都恰好有 2 个子节点，且所有叶子节点距离根节点距离相同。
路径值 指的是路径上所有节点的值之和。

示例 1：

输入：n = 7, cost = [1,5,2,2,3,3,1]
输出：6
解释：我们执行以下的增加操作：
- 将节点 4 的值增加一次。
- 将节点 3 的值增加三次。
- 将节点 7 的值增加两次。
从根到叶子的每一条路径值都为 9 。
总共增加次数为 1 + 3 + 2 = 6 。
这是最小的答案。

示例 2：

输入：n = 3, cost = [5,3,3]
输出：0
解释：两条路径已经有相等的路径值，所以不需要执行任何增加操作。

提示：

3 <= n <= 10⁵
n + 1 是 2 的幂
cost.length == n
1 <= cost[i] <= 10⁴

Submission

运行时间: 107 ms

内存: 23.6 MB

class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int:
        res = 0

        m = len(cost)
        while m > 1:
            k = m // 2
            for j in range(k, m, 2):
                if cost[j] < cost[j+1]:
                    res += cost[j+1] - cost[j]
                    cost[j // 2] += cost[j+1]
                else:
                    res += cost[j] - cost[j+1]
                    cost[j // 2] += cost[j]
            m = k
        return res

Explain

这个题解使用了自底向上的方法来确保所有从根到叶子的路径的值相等。算法从树的最底层（叶子节点）开始，逐层向上调整，使得每个非叶子节点的两个子节点的路径值相等。这是通过将较小的子节点的值增加到较大的子节点的值来实现的。每次操作完成后，将较大的子节点的值累加到父节点上。这样，父节点的值逐渐增加，直到达到根节点。这种方法保证了增加的总次数最小。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int:
        res = 0  # 初始化最小增加操作次数

        m = len(cost)  # 获取节点总数
        while m > 1:  # 只要不是根节点，就继续处理
            k = m // 2  # 下一层的节点数
            for j in range(k, m, 2):  # 遍历当前层的每对节点
                if cost[j] < cost[j+1]:  # 如果左子节点的值小于右子节点
                    res += cost[j+1] - cost[j]  # 增加左子节点的值，使其等于右子节点的值
                    cost[j // 2] += cost[j+1]  # 更新父节点的值
                else:  # 如果右子节点的值小于或等于左子节点
                    res += cost[j] - cost[j+1]  # 增加右子节点的值，使其等于左子节点的值
                    cost[j // 2] += cost[j]  # 更新父节点的值
            m = k  # 处理下一层
        return res  # 返回最小增加操作次数

Explore

这种自底向上的方法可以确保所有从根到叶子的路径在每一步都被平衡调整。如果从根节点开始处理，我们可能会缺少对全局的控制，因为对根节点的调整可能需要在知道所有子树的详细信息后才能正确执行。从叶子节点开始允许我们在每个步骤中具有所有必要的信息，从而可以做出使总代价最小化的决策。这样，每次调整都是基于完整信息的最优决策，避免了顶层决策导致的连锁反应和不必要的多次调整。

题解确实考虑了这个问题，通过始终确保在每层处理时只增加到必须的最小值（即当前两节点中的较大值），从而减少了过度增加的可能性。这种策略意在使得每次操作尽可能地小，防止因逐层累加而导致的不必要增幅。然而，这种方法在确保局部最优（即在当前节点对之间的操作）的同时，也可能不是全局最优解，特别是在极端不平衡的树结构中。

选择将较小值的节点调整到较大值是一种保证操作最小化的策略。若考虑将两个节点的值增加到中间值，可能会导致总体增加的值更大，因为这样做可能需要同时增加两个节点的值。通过只增加一个节点的值至另一个节点的值，可以最小化每一步的增加量，从而降低总体代价。此外，这种方法也简化了算法的实现，因为只需考虑两个节点中的最大值，而无需额外计算一个中间值。

是的，这种方法虽然简单且在很多情况下效果良好，但确实存在导致非最优解的可能性。这是因为直接使用较大值作为父节点的新值，没有考虑可能的其他较小增加值选择，这可能导致在特定树结构中不是最小总增加次数。在某些情况下，更复杂的策略，如基于更广泛的上下文来决定父节点的最终值，可能会找到更小的总增加次数的解决方案。