LeetCode124—Binary Tree Maximum Path Sum
LeetCode124—Binary Tree Maximum Path Sum
原题
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
分析
参考:http://blog.csdn.net/linhuanmars/article/details/22969069
这题确实有点难,刚开始以为树的深度遍历序列中找到和最大子序列,这样进行一次深度优先搜索将结果存在数组中,在对数组做一次最大子序列和运算(考虑节点值可能有负数),然而题目的要求并不是这样的。
题目要求是:要在树中找一条连通的通路,其值最大。
对于树中的某个节点来说,需要考虑两件事情:1是记录到该节点时权值是多少(并实时更新最大值),2是记录经过这个节点的路径来自于左孩子还是右孩子,这两件事情一定要分别计算,最大值要算上左右孩子,但是路径只能是左孩子或者右孩子的其中之一。
代码
class Solution {
int dfs(TreeNode* root,int &maxSum)
{
if (root == NULL)
return 0;
int left = dfs(root->left,maxSum);
int right = dfs(root->right,maxSum);
int rootval = root->val + max(0, left) + max(0,right);
if (maxSum < rootval)
maxSum = rootval;
// return rootval;
return root->val + max(max(left,right),0);
}
public:
int maxPathSum(TreeNode* root) {
int maxSum = root->val;
dfs(root,maxSum);
return maxSum;
}
};
还没有评论,来说两句吧...