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 binary tree
* 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 &depthsum)
{
if(root == NULL)return 0;
if(root->left == NULL && root->right == NULL)
{depthsum = root->val; return root->val;}
int maxsum = 0xC0000000;
int left = 0, lefthalf = 0;
if(root->left)
left = maxpathsum(root->left, lefthalf);
else
{left = 0xC0000000; lefthalf = 0xC0000000;}
int right = 0, righthalf = 0;
if(root->
right)
right = maxpathsum(root->right, righthalf);
else
{right = 0xC0000000; righthalf = 0xC0000000;}
maxsum = lefthalf + root->val + righthalf;
maxsum = left > maxsum left : maxsum;
maxsum = right > maxsum right : maxsum;
lefthalf = lefthalf > righthalf lefthalf : righthalf;
depthsum = lefthalf + root->val > root->val lefthalf+root->val : root->val;
maxsum = maxsum > depthsum maxsum : depthsum;
maxsum = maxsum > root->val maxsum : root->val;
return maxsum;
}
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root == NULL)return 0;
int maxsum = 0;
int depthsum = 0;
maxsum = maxpathsum(root, depthsum);
maxsum = depthsum > maxsum depthsum : maxsum;
return maxsum;
}
};