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. 右子树的最大值；

3. 部分path在左子树，部分path在右子树，经过root；

1与2在递归中计算，为返回值；

3的话需要维护止于root点的最大值，这里用myMax表示（只有一边，止于root）

myMax，可以先求左右myMax的最大值，如果这个值是正数，那么可以把root也算上，不然就直接是root了。

返回值至少是myMax，然后再和左右子树的返回值比，最后和经过root，包含左右子树的情况相比。注意的是排除掉左右子树为空的情况。

代码如下：

1 class Solution { 2 public: 3     int mPS(TreeNode * root, int & myMax) 4     { 5         if( root == NULL ) 6         { 7             return 0; 8         } 9         int left = mPS(root->left, myMax);10         int right = mPS(root->right, myMax);11         int res = root->val;12         if( left > 0 )13         {14             res += left;15         }16         if( right > 0 )17         {18             res += right;19         }20         myMax = max(res, myMax);21         return max(root->val, max(root->val+left,root->val+right));  22     }23     int maxPathSum(TreeNode *root) 24     {25         int myMax = root->val;26         int val =  mPS(root, myMax);27         return max(myMax, val);28     }29 };