我要评论【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 <= 105n + 1是2的幂cost.length == n1 <= cost[i] <= 104
思路
对于某个节点，假设其左子树和右子树都已经“增加”过了（对于左子树，所有路径值相等，右子树同理），但是左子树根到叶路径之和（记为leftsum）和右子树的rightsum不等，我们应该怎么操作呢？
举例说明点我也就是说：
将左右子树路径和之差加到路径和较小的子树的根节点上。
这是因为“加一操作”越靠近根，所能影响的路径数就越多。
方法一：自顶向下的dfs
首先要说明的是这种方法的空间复杂度不如方法二，但是比方法二更容易理解。
我们只需要写一个函数dfs(n)返回节点n（根节点下标从0开始）为根到叶节点的路径之和：
- 时间复杂度 o ( n ) o(n) o(n)，其中 n n n为二叉树节点个数。
- 空间复杂度 o ( log n ) o(\log n) o(logn)，满二叉树的深度是 log n \log n logn级别的。
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 ) o(n) o(n)的空间复杂度。因为往下计算的过程中还要存储当前节点的信息。
因此我们可以倒过来，采用自底向上的方法：
这样相当于是把值存放到 c o s t cost cost数组中了。
- 时间复杂度 o ( n ) o(n) o(n)，其中 n n n为二叉树节点个数。
- 空间复杂度 o ( 1 ) o(1) o(1)，但是我们修改了 c o s t cost cost数组的值。若其值不能被修改，则空间复杂度为 o ( n ) o(n) o(n)（大于方法一的 o ( log n ) o(\log n) o(logn)，因为方法一底部的值向上传递后可以被丢弃）
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
发表评论