题目:
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6
.
代码:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode* root)
{
int max_sum = INT_MIN;
Solution::dfs4MaxSum(root, max_sum);
return max_sum;
}
static int dfs4MaxSum(TreeNode* root, int& max_sum)
{
int ret=;
if ( !root ) return ret;
int l = Solution::dfs4MaxSum(root->left, max_sum);
int r = Solution::dfs4MaxSum(root->right, max_sum);
if ( l> ) ret += l;
if ( r> ) ret += r;
ret += root->val;
max_sum = std::max(ret, max_sum);
return std::max(root->val, std::max(root->val+l, root->val+r));
}
};
tips:
求array最大子序列和是一样的思路。只不过binary tree不是一路,而是分左右两路,自底向上算。
主要注意的地方如下:
1. 维护一个全局最优变量(max_sum),再用ret存放包括前节点在内的局部最大值;每次比较max_sum和ret时,max_sum代表的是不包含当前节点在内的全局最优,ret代表的是一定包含当前节点在内的全局最优。
2. dfs4MaxSum返回时需要注意,left和right只能算一路,不能一起都返到上一层。因为题目中要求的path抻直了只能是一条线,不能带分叉的。
==============================================
第二次过这道题,大体思路有了,细节的错误也都犯了,改过来强化一次AC了。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode* root)
{
int ret = INT_MIN;
if (root) Solution::maxPS(root, ret);
return ret;
}
static int maxPS( TreeNode* root, int& maxSum)
{
if ( !root ) return ;
int l = Solution::maxPS(root->left, maxSum);
int r = Solution::maxPS(root->right, maxSum);
maxSum = max(maxSum, root->val+(l>?l:)+(r>?r:));
return max(root->val,root->val+max(r,l));
}
};
【Binary Tree Maximum Path Sum】cpp的更多相关文章
-
【二叉树的递归】05二叉树中找任意起点和终点使他们的路径和最大【Binary Tree Maximum Path Sum】
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 给定一个二叉树,寻找值最大的路径. ...
-
【leetcode】Binary Tree Maximum Path Sum
Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. The path may start and ...
-
【LeetCode】124. Binary Tree Maximum Path Sum
Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. The path may start and ...
-
[leetcode]Binary Tree Maximum Path Sum
Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. The path may start and ...
-
26. Binary Tree Maximum Path Sum
Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. The path may start and ...
-
leetcode 124. Binary Tree Maximum Path Sum 、543. Diameter of Binary Tree(直径)
124. Binary Tree Maximum Path Sum https://www.cnblogs.com/grandyang/p/4280120.html 如果你要计算加上当前节点的最大pa ...
-
LeetCode: Binary Tree Maximum Path Sum 解题报告
Binary Tree Maximum Path SumGiven a binary tree, find the maximum path sum. The path may start and e ...
-
二叉树系列 - 二叉树里的最长路径 例 [LeetCode] Binary Tree Maximum Path Sum
题目: Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. The path may start ...
-
第四周 Leetcode 124. Binary Tree Maximum Path Sum (HARD)
124. Binary Tree Maximum Path Sum 题意:给定一个二叉树,每个节点有一个权值,寻找任意一个路径,使得权值和最大,只需返回权值和. 思路:对于每一个节点 首先考虑以这个节 ...
随机推荐
-
升级webapi依赖的Newtonsoft.json的版本
随着微软日渐重视开源社区的贡献,微软在自己的产品中往往也会集成开源的第三方库. 比如System.Net.Http.Foramatting.dll 就依赖于Newtonsoft.json v4.5. ...
-
根据包名字符串跳转Activity
/** * 跳转到对应activity */ public void toActivity(Context context,String fullName) { if (className != nu ...
-
C#格式化数值结果表
C#格式化数值结果表 字符 说明 示例 输出 C 货币 string.Format("{0:C3}", 2) $2.000 D 十进制 string.Format("{0 ...
-
MongoDB本地安装与启用(windows )
MongoDB的安装与MongoDB服务配置 Mongo DB 是目前在IT行业非常流行的一种非关系型数据库(NoSql),其灵活的数据存储方式备受当前IT从业人员的青睐.Mongo DB很好的实现了 ...
-
ASP.NET Zero--15.一个例子(8)商品分类管理-权限控制
1.添加权限常量 打开文件AppPermissions.cs [..\MyCompanyName.AbpZeroTemplate.Core\Authorization\AppPermissions.c ...
-
利用MySQL触发器实现check和assertion
MySQL虽然输入check语句不会报错,但是实际上并没有check的功能.但是MySQL 依然可以利用触发器来实现相应功能. 本文将根据两个例子简要阐述MySQL实现check和assertion的 ...
-
前端包管理工具 yarn
yarn 是一个 与 npm 类似的 前端包管理工具 安装 windows 要去官网下载 (一定要去官网下载 .mis 文件进行安装) 用npm 或者 cnpm 也能安装 但是这种安装 有缺 ...
-
layui 文字滚动
将消息标题滚动 上面是效果 <li class="layui-nav-item"> <div class="layui-carousel" i ...
-
bitset,2018蓝桥杯-明码(二进制转换)
bitset可以存储二进制数位 bitset<8> x(2); cout<<x<<endl; //输出:00000010 #include <iostream ...
-
AS3中String转换成Boolean
AS3中, 对布尔值的转换, 规定所有的非空字符串都是true. 下面都不行: var f:Boolean = new Boolean(str); var f:Boolean = str as Boo ...