maxPathSum

https://leetcode.com/problems/binary-tree-maximum-path-sum/
给定一个二叉树，求一个叶子节点到另外一个叶子节点的最大路径和

image.png

int maxDepthRes = Integer.MIN_VALUE;//初始化全局变量，结果为一个最小值

    public int maxPathSum(TreeNode root) {
        maxPathSumHelper(root);
        return maxDepthRes;
    }

    //注意，第一点：以root为根节点的二叉树，计算最大path，可能经过root节点，也可能不经过root节点

    //解释解释，解释这个function
    //这个function是计算 以root为根节点，且经过root节点的path的最大值
    //注意这个function的return是不能以root为根节点形成半环的
    //也就是说  只能是  max(function(root.left),function(root.right)) + root.val

    //所以在计算的过程中，有个全局变量maxDepthRes来算最终的最大值，
    // 因为：最大path，可能经过root节点，也可能不经过root节点
    public int maxPathSumHelper(TreeNode root) {
        if (root == null) {
            return 0;
        }

        //递归调用左子树的最大值
        int left = Math.max(maxPathSumHelper(root.left), 0);

        ////递归调用右子树的最大值
        int right = Math.max(maxPathSumHelper(root.right), 0);

        //left + right + root.val  这个很有意思
        //这个值就是以root为衔接点的半环最大值
        maxDepthRes = Math.max(maxDepthRes, left + right + root.val);

        return Math.max(left, right) + root.val;
    }

参考：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-de-zui-da-lu-jing-he-by-leetcode/