124. 二叉树中的最大路径和

树的遍历一定要用最特殊的情况来推导遍历方式。首先这道题要返回最大路径和，实例1已经很明显了的提示用后序遍历了。而且遍历一定要以最后的节点来作推导，不要用中间的节点来做推导。
既然确定了用后序遍历，剩下的就只剩用在后序遍历代码中去添加相应的条件了。

class Solution {
    public int maxPathSum(TreeNode root) {
        PathFind(root)
    }
    
    public int PathFind(TreeNode root){
        if(root==null) return 0;
        PathFind(root.left);
        PathFind(root.right);
        
        
        
    }
}

接下来就是填充细节了。题意说了路径最少包含一个节点，
那么就有两种情况

1. 只有一个节点
2. 正数节点儿子为负数

所以遍历返回结果的时候，要判断儿子节点的值是否为负数。如果是负数不能和父节点进行相加。
那么就会有一个变量curMax，这个值为当前位置最长路径和，自然就是这样定义——curMax=Math.max(curMax,curMax+leftValue+rightVlaue)，然后就要想着一件事，如向上递归？题目中说要找权重最大的路径，那么就要选择较大的儿子节点return (root.val+Math.max(leftValue+rightValue));
下面是完整代码

class Solution {
    int curMax = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        PathFind(root);
        return curMax;
    }

    public int PathFind(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftValue = Math.max(0, PathFind(root.left));
        int rightValue = Math.max(0, PathFind(root.right));
        curMax = Math.max(root.val + leftValue + rightValue, curMax);
        return Math.max(root.val + leftValue, root.val + rightValue);
    }
}