【C++贪心 DFS】2673. 使二叉树所有路径值相等的最小代价|1917

CSDN 2024-10-19 11:35:01 阅读 61

本文涉及知识点

C++贪心 反证法 决策包容性

C++DFS

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

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

n + 1 是 2 的幂

cost.length == n

1 <= cost[i] <= 104

C++贪心

C++贪心

两轮DFS:

第一轮:后序DFS,求各子树最大路径和并保存,令整棵树路径和的最大值iMax。return 当前节点的值+ max(DFS1(左子树),DFS1(右子树));

第二轮: 前序DFS,当前节点增加:iMax - ( 当前节点的祖先节点和 + 本子树最大路径和)

性质一:由于只能增加,不能减少,所以最终路径和一定大于等于iMax。

性质二:路径和大于iMax,一定不是最优解。如果路径和大于iMax,说明所有路径都加了1,每条路径都减少一个增加的1。如果一条路径有多个节点可以减,减层次最小的(根节点层次最小,叶节点层次最大)。从层次小的节点开始减。这样可以避免某条路径被减少了两次,下面用反证法证明:

令路径p1的节点n1已经减1,给路径p2的节点n2减1的时候,p1再次减一。

\rightarrow

→ n1,n2都是p1的祖先,n2包括p2,n1不包括。

\rightarrow

→ n2的层次 < n1的层次。与假设矛盾。

结论一:最终路径和就是iMax。

如果某条路径需要增加,则在保证不让其他路径超过iMax的情况下,增加层次小的节点。这样可以让更多的路径增加。决策包容性

DFS2(cur,need)

cur += need - 当前子树最大路径值

DFS2(左子树,need-cur)

DFS2(右子树,need-cur)

为了方便计算,可以插入任意一个原始,这样下标就从1开始。

代码

核心代码

<code>class Solution {

public:

int minIncrements(int N, vector<int>& cost) {

cost.insert(cost.begin(), 0);

vector<int> maxs(N + 1);

function<int(int)> DFS1 = [&](int root) {

if (root > N) { return 0; }

return maxs[root] = cost[root] + max(DFS1(root * 2), DFS1(root * 2 + 1));

};

const int iMax = DFS1(1);

int ans = 0;

function<void(int, int)> DFS2 = [&](int root, int need) {

if (root > N) { return; }

const int iAdd = need - maxs[root];

ans += iAdd;

DFS2(2 * root, need - iAdd - cost[root]);

DFS2(2 * root + 1, need - iAdd - cost[root]);

};

DFS2(1, iMax);

return ans;

}

};

单元测试

int n;

vector<int> cost;

TEST_METHOD(TestMethod11)

{

n = 7, cost = { 1, 5, 2, 2, 3, 3, 1 };

auto res = Solution().minIncrements(n, cost);

AssertEx(6, res);

}

TEST_METHOD(TestMethod12)

{

n = 3, cost = { 5,3,3 };

auto res = Solution().minIncrements(n, cost);

AssertEx(0, res);

}

优化(不需要DFS)

任何叶子节点必须和兄弟节点相等,否则这两条路径必定不等。

一,将所有叶子节点增加到和他的兄弟节点相等。

二,令当前树为cur,将各左叶子加到父节节点。删除所有叶子节点,形成新树next。cur符合题意

\iff

⟺ next符合题意。

执行一二,树的最大层次会减少1。不断执行,直到树的层次为1,结束。

无需DFS,直接按节点编号从大到小执行。

class Solution {

public:

int minIncrements(int N, vector<int>& cost) {

cost.insert(cost.begin(), 0);

int ans = 0;

for (int i = N; i > 1; i-=2 ) {

const int iMin = min(cost[i], cost[i - 1]);

const int iMax = max(cost[i], cost[i - 1]);

ans += iMax - iMin;

cost[i / 2] += iMax;

}

return ans;

}

};

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境: VS2022 C++17

如无特殊说明,本算法用**C++**实现。



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。