【递归】C++算法:124 二叉树中的最大路径和

2024-01-06 11:20

本文主要是介绍【递归】C++算法:124 二叉树中的最大路径和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

作者推荐

【动态规划】【字符串】扰乱字符串

本文涉及的基础知识点

递归

124. 二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
是路径中各节点值的总和。
给你一个二叉树的根节点 root ,返回其 最大路径和 。
示例 1:
输入:root = [1,2,3]
输出:6
解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6
示例 2:
输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42
参数范围
树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000

递归

任何路径,必定有且一个节点是路径所有节点的祖先,我们可以枚举路径的祖先节点。故时间复杂度是O(n)。
对于Do函数只考虑本节点及其子孙,不考虑其祖先。

iLeafDirMaxSum以root为起点的最大路径和,必定包括root节点,如果左支或右支的iLeafDirMaxSum较大者为正,则加上。
iRet以root为根的最大路径和,必定包括root节点,如果左支(右支)iLeafDirMaxSum为正,则加上

代码

核心代码

class Solution {
public:int maxPathSum(TreeNode* root) {Do(root);return m_iRet;}int Do(TreeNode* root){if (nullptr == root){return 0;}const int left = Do(root->left);const int right = Do(root->right);int iRet = root->val;if (left >= 0){iRet += left;}if (right >= 0){iRet += right;}m_iRet = max(iRet, m_iRet);std::cout << "root:" << root->val << " ret " << iRet << std::endl;int iLeafDirMaxSum = root->val;const int iMax = max(left, right);if (iMax >= 0){iLeafDirMaxSum += iMax;}return iLeafDirMaxSum;}int m_iRet = -10000'0000;
};

测试用例

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}TreeNode(int x, int iLeft) : val(x), left(new TreeNode(iLeft)), right(nullptr) {}TreeNode(int x, int iLeft, int iRghit) : val(x), left(new TreeNode(iLeft)), right(new TreeNode(iRghit)) {}
};namespace NTree
{TreeNode* Init(const vector<int>& nums, int iNull = 10000){if (0 == nums.size()){return nullptr;}vector<TreeNode*> ptrs(nums.size() + 1), ptrParent(1);for (int i = 0; i < nums.size(); i++){if (iNull == nums[i]){continue;}const int iNO = i + 1;ptrs[iNO] = new TreeNode(nums[i]);ptrParent.emplace_back(ptrs[iNO]);if (1 == iNO){continue;}if (iNO & 1){//奇数是右支ptrParent[iNO / 2]->right = ptrs[iNO];}else{ptrParent[iNO / 2]->left = ptrs[iNO];}}return ptrs[1];}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}
}int main()
{string s,t;	const int null = -10000;{Solution sln;vector<int> nums = { 1,2,3 };auto root = NTree::Init(nums, null);auto res = sln.maxPathSum(root);Assert(6, res);}{Solution sln;vector<int> nums = { -10,9,20,null,null,15,7 };auto root = NTree::Init(nums, null);auto res = sln.maxPathSum(root);Assert(42, res);}}

2023年1月代码

/**

  • Definition for a binary tree node.
  • struct TreeNode {
  • int val;
    
  • TreeNode *left;
    
  • TreeNode *right;
    
  • TreeNode() : val(0), left(nullptr), right(nullptr) {}
    
  • TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    
  • TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    
  • };
    */

class Solution {
public:
int maxPathSum(TreeNode* root) {
Sum(root);
return m_iRet;
}
int Sum(TreeNode* node)
{
if (nullptr == node)
{
return 0;
}
std::multiset setLeftRight;
setLeftRight.insert(Sum(node->left));
setLeftRight.insert(Sum(node->right));
if (*setLeftRight.begin() > 0)
{
m_iRet = max(m_iRet, node->val + *setLeftRight.begin() + *setLeftRight.rbegin());
}
if (*setLeftRight.rbegin() > 0)
{
m_iRet = max(m_iRet, node->val + *setLeftRight.rbegin());
return node->val + setLeftRight.rbegin();
}
m_iRet = max(m_iRet, node->val);
return node->val;
}
int m_iRet = INT_MIN;
std::unordered_map<TreeNode
, std::set> m_mapTop2Dis;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

这篇关于【递归】C++算法:124 二叉树中的最大路径和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

python设置环境变量路径实现过程

《python设置环境变量路径实现过程》本文介绍设置Python路径的多种方法:临时设置(Windows用`set`,Linux/macOS用`export`)、永久设置(系统属性或shell配置文件... 目录设置python路径的方法临时设置环境变量(适用于当前会话)永久设置环境变量(Windows系统

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发;同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()?它的作用是什么?类比一下:二、join()的作用总结三、join()怎么

Spring Boot中的路径变量示例详解

《SpringBoot中的路径变量示例详解》SpringBoot中PathVariable通过@PathVariable注解实现URL参数与方法参数绑定,支持多参数接收、类型转换、可选参数、默认值及... 目录一. 基本用法与参数映射1.路径定义2.参数绑定&nhttp://www.chinasem.cnbs

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window