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

Return6.

 思路：题目中说明起始节点可以是任意节点，所以，最大的路径和不一样要经过root，可以是左子树中某一条，或者是右子树中某一条，当然也可能是经过树的根节点root的。递归式是应该是这三者中选出最大者。这题是看完yucoding的博客才算可能理解，这里只是用中文讲解该博客中的分析过程。举例子：

对树中的任一节点，当有一条路径经过它时（不一定为最大），有两种情况：

1)“根节点”为当前节点时，如当前节点为2时，路径为6->4->2->5->-3；

2)“根节点”为当前节点的父节点，如当前节点为2时，路径为-3->5->2->1->-3->6

对某个节点a，最大路径为：

i) max_top(a)为第一种情况下的最大路径和；

ii) max_single(a)为第二种情况下的最大路径和；

则，max_top(a)=Max{max_single(a), max_single(a->left)+max_single(a->right)+a->val, a->val};

     max_single(a)=Max{max_single(a->left)+a->val, max_single(a->right)+a->val, a->val};

最每个节点a，res=max(res, max_top(a))。

其实，个人这样理解的，max_single(a)，为先找到一个“根节点”两边的选出较大的，然后考虑三者中最大。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution 
{
public:
    //使用dfs
    int maxPathSum(TreeNode *root)
    {
        maxSum=root->val;
        maxChildSum(root);
        return maxSum;

    }
private:
    int maxSum;
    int maxChildSum(TreeNode* root)
    {
        if(root==NULL)   return 0;
        
        int l=maxChildSum(root->left);
        int r=maxChildSum(root->right);

        int sum=root->val;
        if(l>0) sum+=l;
        if(r>0) sum+=r;
        maxSum=max(maxSum,sum);
       
        return max(r,l)>0?max(r,l)+root->val:root->val;
    }
};

[Leetcode] Binary tree maximum path sum求二叉树最大路径和