43.Binary Tree Maximum Path Sum-二叉树中的最大路径和

题目描述：


解析：
_递归终止条件：
如果root为null，直接返回0。
递归过程：
1.递归求解包含左孩子的以左孩子为根结点的最大路径和maxL，以及包含右孩子的以右孩子为根结点的最大路径和maxR。
2.如果maxL > 0，我们的当前的最大路径和就应该加上maxL。
3.如果maxR > 0，我们的当前的最大路径和就应该加上maxR。
4.最大路径和result取result和当前最大路径和的较大值。
5.该递归函数的返回结果应该是root的值，root的值加上maxL的值，root的值加上maxR的值，这三者间的较大值。

_

class Solution {
    int result = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxSum(root);
        return result;
    }
    private int maxSum(TreeNode root) {  //求包含root根节点的最大路径和
        if (root == null) return 0;
        int data=root.val;
        int maxL=maxSum(root.left);
        if(maxL>0) data+=maxL;
        int maxR=maxSum(root.right);
        if(maxR>0) data+=maxR;
        result = Math.max(result,data); //记录当前树的最大路径和
        return Math.max(root.val,Math.max(root.val+maxL, root.val+maxR));
    }
}