题目：
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.
解题思路：
最长路径和要分几种情况考虑，对于这样一个节点
cur
/ \
left right
设left是左子树的最长路径和，right是右子树的最长路径和，要求当前节点的最长路径和，只要将1、当前节点的val值2、当前节点val值加上left 3、当前节点val值加上rihgt，取其最大者作为当前节点的最长路径和。
以上我们只是考虑了三种情况，1、最长路径是从cur节点开始；2、最长路径从左边上来经过cur；3、最长路径从右边上来经过cur
还有三种情况需要考虑，1、如果left值是最长路径呢，即最长路径不经过cur，到left就为止了；2、如果right值是最长路径呢？3、最长路径经过cur，但是没有向上走，而是向另一个分支去了呢（left or right）？
所以我们需要定义一个全局参数，求出left，right，及left+right+cur值的最大值，最后与递归结束后过根节点的最长路径长度比较，取其大者为此题答案。
实现代码：
class Solution {
public:
int maxPathSum(TreeNode *root) {
if(root == NULL)
return 0;
int maxsum = INT_MIN;
int ret = getMax(root, maxsum);
return max(ret, maxsum);
}
int getMax(TreeNode *root, int &maxsum)
{
if(root == NULL)
return INT_MIN>>4;
int leftmax = getMax(root->left, maxsum);
int rightmax = getMax(root->right, maxsum);
maxsum = max(maxsum, max(max(leftmax, rightmax), leftmax + root->val + rightmax));
return max(root->val, max(leftmax, rightmax) + root->val);
}
};