本文主要是介绍【递归】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 二叉树中的最大路径和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
