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

本文主要是介绍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 <= 105
  • n + 1 是 2 的幂
  • cost.length == n
  • 1 <= cost[i] <= 104

思路

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

举例说明点我

例如如下二叉树中

   15   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开始)为根到叶节点的路径之和:

  1. 递归左子树得到leftSum,递归右子树得到rightSum

  2. leftSumrightSum之差累加到答案中

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

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

  • 时间复杂度 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;}/*01   23 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)的空间复杂度。因为往下计算的过程中还要存储当前节点的信息。

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

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

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

  3. 这个节点的两个子节点的最大值累加到这个节点(路径累加)

这样相当于是把值存放到 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 Listclass Solution:def minIncrements(self, n: int, cost: List[int]) -> int:ans = 0for 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

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/136357361

这篇关于LeetCode 2673.使二叉树所有路径值相等的最小代价:自顶向下的DFS 或 自底向上的递推的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/756994

相关文章

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径,

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》:本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较:二、开始比较总结概要公司存在多

windos server2022里的DFS配置的实现

《windosserver2022里的DFS配置的实现》DFS是WindowsServer操作系统提供的一种功能,用于在多台服务器上集中管理共享文件夹和文件的分布式存储解决方案,本文就来介绍一下wi... 目录什么是DFS?优势:应用场景:DFS配置步骤什么是DFS?DFS指的是分布式文件系统(Distr

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W