Question ：

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

.

Anwser 1 ：

/**
  * 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 calLen(TreeNode *root, int &len)
     {
         if (root == NULL)
         {
             len = 0;
             return 0;
         }
         
         if (root->left == NULL && root->right == NULL)
         {
             len = root->val;
             return root->val;
         }
         
         int leftPath, rightPath;
         int leftLen;
         if (root->left)
             leftLen = calLen(root->left, leftPath);
         else
         {
             leftLen = INT_MIN;
             leftPath = 0;
         }
         
         int rightLen;
         if (root->right)
             rightLen = calLen(root->right, rightPath);
         else
         {
             rightLen = INT_MIN;
             rightPath = 0;
         }
         
         len = max(max(leftPath, rightPath) + root->val, root->val);
         int maxLen = max(root->val, max(leftPath + rightPath + root->val, 
             max(leftPath + root->val, rightPath + root->val)));
         
         return max(max(leftLen, rightLen), maxLen);
     }
     
     int maxPathSum(TreeNode *root) {
         // Start typing your C/C++ solution below
         // DO NOT write int main() function
         int len;
         return calLen(root, len);
     }
 };