LeetCode 2673.使二叉树所有路径值相等的最小代价：自顶向下的DFS 或自底向上的递推

【LetMeFly】2673.使二叉树所有路径值相等的最小代价：自顶向下的DFS 或自底向上的递推

力扣题目链接：https://leetcode.cn/problems/make-costs-of-paths-equal-in-a-binary-tree/

给你一个整数 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⁴

思路

对于某个节点，假设其左子树和右子树都已经“增加”过了（对于左子树，所有路径值相等，右子树同理），但是左子树根到叶路径之和（记为leftSum）和右子树的rightSum不等，我们应该怎么操作呢？

举例说明点我

例如如下二叉树中
   1
 5   2
2 3 3 1
的根节点1，假设其左子树已经由
 5
2 3
变成了
 5
3 3
，而右子树已经由
 2
3 1
变成了
 2
3 3
那么我们应该如何进行下一步操作呢？

对于根节点1：其左子树已经平衡，路径之和为5 + 3 = 8；其右子树已经平衡，路径之和为2 + 3 = 5。

想要让左右子路径之和相等？当然只要右子的根节点+3即可。

也就是说：

将左右子树路径和之差加到路径和较小的子树的根节点上。

这是因为“加一操作”越靠近根，所能影响的路径数就越多。

方法一：自顶向下的DFS

首先要说明的是这种方法的空间复杂度不如方法二，但是比方法二更容易理解。

我们只需要写一个函数dfs(n)返回节点n（根节点下标从0开始）为根到叶节点的路径之和：

递归左子树得到leftSum，递归右子树得到rightSum

将leftSum和rightSum之差累加到答案中

返回max(leftSum, rightSum) + cost[n]作为该节点到叶节点的路径之和

终止条件：n超出数组范围

时间复杂度 $O (N)$ ，其中 $N$ 为二叉树节点个数。
空间复杂度 $O(\log N)$ ，满二叉树的深度是 $\log N$ 级别的。

AC代码

C++

class Solution {
private:
    int ans;

    int dfs(int n, vector<int>& cost) {
        if (n >= cost.size()) {
            return 0;
        }
        /*
               0
             1   2
            3 4 5 6
        */
        int leftSum = dfs(n * 2 + 1, cost);
        int rightSum = dfs(n * 2 + 2, cost);
        ans += max(leftSum, rightSum) - min(leftSum, rightSum);
        return max(leftSum, rightSum) + cost[n];
    }
public:
    int minIncrements(int n, vector<int>& cost) {
        ans = 0;
        dfs(0, cost);
        return ans;
    }
};

方法二：自底向上的递推

自底向上

在自顶向下的方法一中，递归占用了 $O (N)$ 的空间复杂度。因为往下计算的过程中还要存储当前节点的信息。

因此我们可以倒过来，采用自底向上的方法：

从最后一个非叶节点开始往根节点遍历

这个节点的两个子节点之差累加到答案

这个节点的两个子节点的最大值累加到这个节点（路径累加）

这样相当于是把值存放到 $cos t$ 数组中了。

时间复杂度 $O (N)$ ，其中 $N$ 为二叉树节点个数。
空间复杂度 $O (1)$ ，但是我们修改了 $cos t$ 数组的值。若其值不能被修改，则空间复杂度为 $O (N)$ （大于方法一的 $O(\log N)$ ，因为方法一底部的值向上传递后可以被丢弃）

AC代码

C++

class Solution {
public:
    int minIncrements(int n, vector<int>& cost) {
        int ans = 0;
        for (int i = n / 2 - 1; i >= 0; i--) {
            ans += abs(cost[i * 2 + 1] - cost[i * 2 + 2]);
            cost[i] += max(cost[i * 2 + 1], cost[i * 2 + 2]);
        }
        return ans;
    }
};

Python

# from typing import List

class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int:
        ans = 0
        for i in range(n // 2 - 1, -1, -1):
            ans += abs(cost[i * 2 + 1] - cost[i * 2 + 2])
            cost[i] += max(cost[i * 2 + 1], cost[i * 2 + 2])
        return ans