124. 二叉树中的最大路径和
程序员文章站
2022-05-20 14:06:02
...
给定一个非空二叉树,返回其最大路径和。
本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
-10
/
9 20
/
15 7
输出: 42
我的代码
static int x=[]()
{
std::ios::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}();
int sum;
int dfs(TreeNode* root)
{
if(root==NULL)
return 0;
else
{
int m=dfs(root->left);
int n=dfs(root->right);
int t=root->val;
int temp_sum=max(t+m+n,max(t,max(t+m,t+n)));
sum=max(sum,temp_sum);
return max(t,max(t+m,t+n));
}
}
class Solution {
public:
int maxPathSum(TreeNode* root) {
sum=INT_MIN;
int b=dfs(root);
return sum;
}
};
上一篇: LeetCode(145)-二叉树后序遍历(递归、非递归)
下一篇: 45. 跳跃游戏 II
推荐阅读
-
Winform中在使用VS+svn进行协同开发时添加引用时的相对路径和绝对路径的问题
-
ThinkPHP中公共函数路径和配置项路径的映射分析
-
win10系统中如何解决cmd中的路径和现在电脑的用户名不一致
-
Python利用前序和中序遍历结果重建二叉树的方法
-
ASP 包含文件中的路径问题和使用单一数据库连接文件的解决方案
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现
-
python3实现在二叉树中找出和为某一值的所有路径
-
【算法】二叉树的前序、中序、后序、层序遍历和还原。
-
insert和select结合实现"插入某字段在数据库中的最大值+1"的方法