题目描述

给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。
这个路径的开始节点和结束节点可以是二叉树中的任意节点
例如：
给出以下的二叉树，
 
返回的结果为6

一个节点的最大值  可以是自己    root + left    root + right     root+left + right;
如果子节点为负数节点    让他的计算值为0     则一个节点的最大值为 root+left + right
爷爷节点 与孙子节点连接的最大值 为 gp + p +left          或者   gp +p + right

//设置一个全局变量用来存储 节点之和的最大值
int max = Integer.MINVALUE;

public int maxPathSum(TreeNode root) {
        // 当根节点为null时返回0
        if (root == null) {
            return 0;
        }
        help(root);
        return max;
    }

public int help(TreeNode root) {
         if(root == null) {
             return 0;
         }
//如果子节点为负数节点    让他的计算值为0     则一个节点的最大值为 root+left + right
         int left = Math.max(help(root.left), 0);   
         int right = Math.max(help(root.right), 0);
         max = Math.max(max, root.val + left + right);
         return  Math.max(root.val + left, root.val + right);
    }