LeetCode题目：Binary Tree Maximum Path Sum

By | 2012 年 12 月 9 日

1.终止在这个节点上（往自己子树走）的最大路径值是多少
2.经过这个节点的最大值是多少？（从左子树走过自己到右子树）
3.不经过此节点的子树中可能获得的最大值是多少？

1.终止在此节点的最大路径，首先是自己的值包含进去，然后如果终止在左或右子树的根节点的最大路径值大于0的话，加上这个值。
2.经过这个节点的最大值，很简单了，左右子树的端点最大值加上自己的值。
3.不经过此节点的最大值，直接查看左右子树中的这个值（如果有左右子树的话），还有左右子树的端点最大值。

2013-1-18，更新了一个更简单的办法.

Question: Binary Tree Maximum Path Sum

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.

代码:

248ms过大集合

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Maxes{
public:
int tmax;//max of terminated in self
int pmax;//max of pass self
int nmax;//max of non-relative to self
Maxes() {tmax = pmax = 0; nmax = (1 << (sizeof(int) * 8 - 1));}
inline int getMax() {
int m = tmax;
if(m < pmax) m = pmax;
if(m < nmax) m = nmax;
return m;
}
};
class Solution {
public:
Maxes maxPath(TreeNode *root) {
Maxes m;
if(NULL == root)
return m;

Maxes l = maxPath(root->left);
Maxes r = maxPath(root->right);

//tmax is the max value which terminated at this node
//when all of it's children is negative, this is it's value
//or add the max value terminated at it's children
m.tmax = max(l.tmax,r.tmax);
if(m.tmax < 0) m.tmax = 0;
m.tmax += root->val;

//pmax is the max value which is pass this node
//that is it's value terminated at it's children (if have, or zero), add self value
m.pmax = l.tmax + r.tmax + root->val;

//nmax is the max value which not including current node
if(root->left)
m.nmax = l.getMax();
if(root->right) {
int rmax = r.getMax();
if(m.nmax < rmax) m.nmax = rmax;
}
return m;
}
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
Maxes m = maxPath(root);
int ma = m.getMax();
return ma;
}
};
```

Code rewrite at 2013-1-18, 266ms pass large set, simpler

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
int _curMax;
//return the max path ending in root
//and refresh the _curMax with the path sum that go through from left to root to right child.
int maxWithRoot(TreeNode *root) {
if(NULL == root) return 0;
int leftmax = maxWithRoot(root->left);
int rightmax = maxWithRoot(root->right);

//the max from left child to right child, accross from root
int arcmax = root->val;
if(leftmax > 0) arcmax += leftmax;
if(rightmax > 0) arcmax += rightmax;
if(_curMax < arcmax) _curMax = arcmax;

//the max that end in root
int pathmax = root->val;
int submax = std::max(leftmax,rightmax);
if(submax > 0) pathmax += submax;
if(_curMax < pathmax) _curMax = pathmax;

return pathmax;
}
public:
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
_curMax = INT_MIN;
maxWithRoot(root);
return _curMax;
}
};
```

5 thoughts on “LeetCode题目：Binary Tree Maximum Path Sum”

1. JamesFreeman

非常清楚！而且有思路进展历程和事后refactory，牛！

2. logicmd

这题不会做，翻到贵blog，发觉
Code rewrite at 2013-1-18部分中
一定有`arcmax <= pathmax`

`if(_curMax < pathmax) _curMax = pathmax;`
这句可以不要