``````Given a non-empty 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 must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

1
/ \
2   3

Output: 6
Example 2:

Input: [-10,9,20,null,null,15,7]

-10
/ \
9  20
/  \
15   7

Output: 42``````

``````/**
* 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 {
int maxPathSum(TreeNode *root, int &re) {
if(NULL == root)
{
return 0;
}

int l = maxPathSum(root->left,re);
int r = maxPathSum(root->right,re);

l = (l < 0) ? 0 : l;
r = (r < 0) ? 0 : r;

if(l + r + root->val > re)
re = l + r + root->val;

return root->val += max(l, r);
}
public:
int maxPathSum(TreeNode* root) {
int max = INT_MIN;
maxPathSum(root, max);

return max;
}
};``````

``````/**
* 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 {
int maxPathSum(TreeNode *root, int &re) {
if(NULL == root)
{
printf("call func maxPathSum,root NULL,re = %d.\n",re);
return 0;
}

printf("call func maxPathSum,root->val:%d,re = %d.\n",root->val,re);
int l = maxPathSum(root->left,re);
int r = maxPathSum(root->right,re);

l = (l < 0) ? 0 : l;
r = (r < 0) ? 0 : r;

if(l + r + root->val > re)
re = l + r + root->val;

int res = root->val + max(l, r);
printf("return func l:%d,r:%d,val:%d,re:%d,res:%d\n",l,r,root->val,re,res);
return res;
}
public:
int maxPathSum(TreeNode* root) {
int max = INT_MIN;
maxPathSum(root, max);

return max;
}
};``````

``````call func maxPathSum,root->val:-10,re = -2147483648.
call func maxPathSum,root->val:9,re = -2147483648.
call func maxPathSum,root NULL,re = -2147483648.
call func maxPathSum,root NULL,re = -2147483648.
return func l:0,r:0,val:9,re:9,res:9
call func maxPathSum,root->val:20,re = 9.
call func maxPathSum,root->val:15,re = 9.
call func maxPathSum,root NULL,re = 9.
call func maxPathSum,root NULL,re = 9.
return func l:0,r:0,val:15,re:15,res:15
call func maxPathSum,root->val:7,re = 15.
call func maxPathSum,root NULL,re = 15.
call func maxPathSum,root NULL,re = 15.
return func l:0,r:0,val:7,re:15,res:7
return func l:15,r:7,val:20,re:42,res:35
return func l:9,r:35,val:-10,re:42,res:25``````