二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1

      / \

     2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

   -10

   / \

  9  20

    /  \

   15   7

输出: 42

思路1 递归

根据题意，最大路径和可能出现在：

左子树中

右子树中

包含根节点与左右子树

我们的思路是递归从bottom向topreturn的过程中，记录左子树和右子树中路径更大的那个，并向父节点提供当前节点和子树组成的最大值。

递归设计：

返回值：(root.val) + max(left, right) 即此节点与左右子树最大值之和，较差的解直接被舍弃，不会再被用到。

需要注意的是，若计算结果tmp <= 0，意味着对根节点有负贡献，不会在任何情况选这条路（父节点中止），因此返回0。

递归终止条件：越过叶子节点，返回0；

记录最大值：当前节点最大值 = root.val + left + right。

最终返回所有路径中的全局最大值即可。

static private int maxSum;
public static int maxPathSum(TreeNode root) {
    maxSum  = Integer.MIN_VALUE;
    helper(root);
    return maxSum;
}
private static int helper(TreeNode node){
    if(node == null){
        return 0;
    }
    int leftSum = Math.max(helper(node.left),0);
    int rightSum = Math.max(helper(node.right),0);
    maxSum = Math.max(leftSum+rightSum+node.val,maxSum);
    return Math.max(leftSum,rightSum)+node.val;
}

这里有个问题就是为什么要

maxSum  = Integer.MIN_VALUE;

//这里为什么要进行初始化为Integer.MIN_VALUE  是因为有的点是负数，万一树全是负数呢

思路2

public static int maxPathSum(TreeNode root) {
    if(root == null){
        return 0;
    }
    int[] maxPath = new int[]{Integer.MIN_VALUE};
    dfs(root,maxPath);
    return maxPath[0];
}

/**
 * @Author liuhaidong
 * @Description 以root为顶点的直上直下的path中path sum 最大的一条值
 * @param
 * @Date 15:36 2019/10/8 0008
 */
private static int dfs(TreeNode root, int[] maxPath) {

    int left = root.left != null ? Math.max(dfs(root.left,maxPath),0): 0;
    int right = root.right != null ? Math.max(dfs(root.right,maxPath),0): 0;
    //并且以上两个还满足当前为叶子节点的时候再往下传了
    int cur = root.val + left + right;
    maxPath[0] = Math.max(maxPath[0],cur);
    return root.val + Math.max(left,right);
}

这里有个问题就是为什么传进来的是一个数组，

因为如果传进来的是一个数的话会被改变值，只有设置成全局变量或者是数组的话就不会改变。

向方法中传递数组

在java中，所有对象都是通过引用进行操作的。而数组也是一种对象，当把数组作为参数传递给方法时，传递的实际上就是数组对象的引用。在方法中对数组的所有操作，都会映射到原数组中。而所谓的"引用"，就是java对象在堆内存的地址赋给了多个"栈内存"的变量。

主函数

public static void main(String[] args) {
    TreeNode root = new TreeNode(5);
    TreeNode node1 = new TreeNode(4);
    TreeNode node2 = new TreeNode(8);
    TreeNode node3 = new TreeNode(11);
    TreeNode node4 = new TreeNode(7);
    TreeNode node5 = new TreeNode(2);
    TreeNode node6 = new TreeNode(13);
    TreeNode node7 = new TreeNode(4);
    TreeNode node8 = new TreeNode(1);
    root.left=node1;
    root.right=node2;
    node1.left=node3;
    node3.left=node4;
    node3.right=node5;
    node2.left=node6;
    node2.right=node7;
    node7.right=node8;
    System.out.println(maxPathSum(root));
}