题目：

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

思路：刚开始思路理解错误，理解为从根节点到所有的叶子节点的所有路径中，最大的路径和。如果是这样，代码如下；

void helper_sum(BinTree* root,vector<int>& path,int& maxsum)
{
    if(root == NULL)
        return ;
    path.push_back(root->value);
    if(root->left == NULL && root->right == NULL)
    {
        int tmp=0;
        for(int i=0;i<path.size();i++)
        {
            tmp += path[i];
            cout<<path[i]<<" ";
        }
        cout<<"tmp is "<<tmp<<endl; 
        cout<<endl;
        maxsum  = max(tmp,maxsum);
    //    cout<<"tmp is "<<tmp<<endl; 
        //return ;
    }
    helper_sum(root->left,path,maxsum);
    helper_sum(root->right,path,maxsum);
    path.pop_back();
}
int MaxPathSum(BinTree* root)
{
    if(root == NULL)
        return 0;
    vector<int> path;
    int maxsum=0;
    helper_sum(root,path,maxsum);
    return maxsum;
}

求出所有的根节点到叶子接到的路径和，找到最大的即可。

如果按照题意要求，那么从任意一个节点开始，任意一个节点结束，那么可能会出现下面的情况，最大的路径不经过根节点，最大的路径经过根节点。

如果最大的路径不经过根节点，那么最大的路径要么在左子树中，要么在右子树中，如果经过根节点，那么左子树最大+右子树最大+根节点的值。

最终的结果是取三个之最。

这道题是求树的路径和的题目，不过和平常不同的是这里的路径不仅可以从根到某一个结点，而且路径可以从左子树某一个结点，然后到达右子树的结点，就像题目中所说的可以起始和终结于任何结点。在这里树没有被看成有向图，而是被当成无向图来寻找路径。因为这个路径的灵活性，我们需要对递归返回值进行一些调整，而不是通常的返回要求的结果。在这里，函数的返回值定义为以自己为根的一条从根到子结点的最长路径（这里路径就不是当成无向图了，必须往单方向走）。这个返回值是为了提供给它的父结点计算自身的最长路径用，而结点自身的最长路径（也就是可以从左到右那种）则只需计算然后更新即可。这样一来，一个结点自身的最长路径就是它的左子树返回值（如果大于0的话），加上右子树的返回值（如果大于0的话），再加上自己的值。而返回值则是自己的值加上左子树返回值，右子树返回值或者0（注意这里是“或者”，而不是“加上”，因为返回值只取一支的路径和）。在过程中求得当前最长路径时比较一下是不是目前最长的，如果是则更新。算法的本质还是一次树的遍历，所以复杂度是O(n)。而空间上仍然是栈大小O(logn)。代码如下：

/ 返回以root为根的最大和的一条单向路径 
int MaxSum(BinTree* root,int& maxsum)
{
    if(root == NULL)
     return 0;
    int maxleft= MaxSum(root->left,maxsum);
    int maxright = MaxSum(root->right,maxsum);
    int cur = root->value +max(maxright,0)+max(maxleft,0);
    maxsum = max(maxsum,cur);
    return root->value+max(maxright,max(maxleft,0));
}
int MaxPahtSum(BinTree* root)
{
    if(root == NULL)
     return 0;
    int sum = root->value;
    MaxSum(root,sum);
    return sum;
}