给定一棵二叉树，求各个路径的最大和。

	



	// 获得包含该结点的最大和



	int help(TreeNode *root, int &m) { 



	    if(root == 0) return 0;  



	    int l = help(root->left, m); // 获得该结点左子树最大和  



	    int r = help(root->right, m);// 获得该结点右子树最大和 



	  



	    // 取左右子树和中较大的那个，如果都小于0，则左右子树都舍弃 



	    int ret = max(max(l, r), 0) + root->val;   



	    // 列举三种结果并与最大值做比较



	    m = max(m, max(ret, l + r + root->val));  



	    return ret;



	} 



	  



	intmaxPathSum(TreeNode *root) {



	  int max = root->val;



	  // help中max参数为引用，可视为全局变量



	  help(root, max);



	  return max;



	}

/*问题描述:
给定一棵二叉树，求各个路径的最大和，路径可以以任意结点作为起点和终点。
解决思路：
本题可以通过对二叉树进行后序遍历来解决，具体思路如下：
对于当前遍历到的结点root，假设已经求出在遍历root结点前最大的路径和为max：
1）求出以root->left为起始结点，叶子结点为终结点的最大路径和为sumLeft。
2）同理求出以root->right为起始结点，叶子结点为终结点的最大路径和sumRight。
包含root结点的最长路径可能包含如下三种情况：
1）leftMax=root->val+sumLeft（右子树最大路径和可能为负）。
2）rightMax=root->val+sumRight（左子树最大路径和可能为负）。
3）allMax=root->val+sumLeft+sumRight（左右子树的最大路径和都不为负）。
因此，包含root结点的最大路径和为tmpMax=max(leftMax,rightMax,allMax)。
在求出包含root结点的最大路径后，如果tmpMax>max，则更新最大路径和为tmpMax。
*/
#include <iostream> 
#include <limits.h> 
using namespace std;  
struct TreeNode  
{  
    int val;  
    TreeNode *left;  
    TreeNode *right;  
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
};  
/*求a，b，c的最大值*/  
int Max(int a, int b, int c)  
{  
    int max = a>b ? a : b;  
    max = max>c ? max : c;  
    return max;  
}  
/*寻找最长路径*/  
int findMaxPathrecursive(TreeNode* root, int &max)  
{  
    if (NULL == root)  
    {  
        return 0;  
    }  
    else  
    {  
        //求左子树以root->left为起始结点的最大路径和  
        int sumLeft = findMaxPathrecursive(root->left, max);  
        //求右子树以root->right为起始结点的最大路径和  
        int sumRight = findMaxPathrecursive(root->right, max);  
        //求以root为起始结点，叶子结点为结束结点的最大路径和  
        int allMax = root->val + sumLeft + sumRight;  
        int leftMax = root->val + sumLeft;  
        int rightMax = root->val + sumRight;  
        int tmpMax = Max(allMax, leftMax, rightMax);  
        if (tmpMax>max)  
            max = tmpMax;  
        int subMax = sumLeft > sumRight ? sumLeft : sumRight;  
        //返回以root为起始结点，叶子结点为结束结点的最大路径和  
        return root->val + subMax;  
    }  
}  
int findMaxPath(TreeNode* root)  
{  
    int max = INT_MIN;  
    int a=findMaxPathrecursive(root, max);  
    cout<<"a:"<<a<<endl;
    return max;  
}  
int main()  
{  
    TreeNode* root0 = new TreeNode(-2);  
    TreeNode* left01 = new TreeNode(-5);  
    TreeNode* right02 = new TreeNode(-3);   
    TreeNode* left11 = new TreeNode(-6);  
    TreeNode* right12 = new TreeNode(-2); 
    TreeNode* left21 = new TreeNode(-7);  
    TreeNode* right22 = new TreeNode(-3);
    root0->left = left01;  
    root0->right = right02;
    left01->left =left11;
    left01->right=right12;
    right02->left=left21;
    right02->right=right22;
    cout << findMaxPath(root0) << endl;  
    return 0;  
} 

public class Binary_Tree_Maximum_Path_Sum {
    public int max = Integer.MIN_VALUE;
    public int findRst(TreeNode root){
        if (root == null) {
            return 0;
        } else {
            int sumLeft = findRst(root.left);
            int sumRight = findRst(root.right);
            int cur = root.val;
            int leftRightSum = sumLeft+cur+sumRight;
            max = max<leftRightSum?leftRightSum:max;
            int subMax = sumLeft > sumRight ? sumLeft : sumRight;

            if (cur+subMax > 0) {
                if(max<subMax+cur)
                    max = subMax+cur;
                return cur + subMax;
            } else {
                return 0;
            }
        }
    }
    public int maxPathSum(TreeNode root) {
        if(root==null)
            return 0;
        max = max<root.val?root.val:max;
        findRst(root);
        return max;
    }

    public static void main(String[] args){
        Binary_Tree_Maximum_Path_Sum binary_tree_maximum_path_sum = new Binary_Tree_Maximum_Path_Sum();
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(-1);
        root.left.left = new TreeNode(-4);
        root.left.right = new TreeNode(99);
        root.right = new TreeNode(-3);
        root.right.left = new TreeNode(-5);
        root.right.right = new TreeNode(-6);
        System.out.println(binary_tree_maximum_path_sum.maxPathSum(root));
    }
}

    if (root)
         return 0;
    if (root->left)
        l = maxPathSum(root->left)+root->val;
    if (root->right)
        r = maxPathSum(root->right)+root->val;
    if (l+r-root->val>maxSum)
        maxSum = l+r-root->val;
    return l>r?l:r;