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.

1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     int calLen(TreeNode *root, int &len)13     {14         if (root == NULL)15         {16             len = 0;17             return 0;18         }19         20         if (root->left == NULL && root->right == NULL)21         {22             len = root->val;23             return root->val;24         }25         26         int leftPath, rightPath;27         int leftLen;28         if (root->left)29             leftLen = calLen(root->left, leftPath);30         else31         {32             leftLen = INT_MIN;33             leftPath = 0;34         }35         36         int rightLen;37         if (root->right)38             rightLen = calLen(root->right, rightPath);39         else40         {41             rightLen = INT_MIN;42             rightPath = 0;43         }44         45         len = max(max(leftPath, rightPath) + root->val, root->val);46         int maxLen = max(root->val, max(leftPath + rightPath + root->val, 47             max(leftPath + root->val, rightPath + root->val)));48         49         return max(max(leftLen, rightLen), maxLen);50     }51     52     int maxPathSum(TreeNode *root) {53         // Start typing your C/C++ solution below54         // DO NOT write int main() function55         int len;56         return calLen(root, len);57     }58 };