一、题目

　　1、审题

　　2、分析

　　　　给出一棵二叉树，求一条路径使得其通过的节点数值和最大为多少。

 

 二、解答

　　1、思路：　

　　　　方法一、

　　　　　　①、通过递归 求得 root 左子树的最大和，root 右子树的最大和；

　　　　　　②、采用一个全局变量记录最大节点数之和；

　　　　　　③、跳出递归条件为 root == null；

int maxValue ;    public int maxPathSum(TreeNode root) {        maxValue = Integer.MIN_VALUE;        maxPathDown(root);        return maxValue;    }    private int maxPathDown(TreeNode root) {                if(root == null)            return 0;        int left = Math.max(0, maxPathDown(root.left)); // 左子树的最大路径和        int right = Math.max(0, maxPathDown(root.right)); // 右子树的最大路径和        maxValue = Math.max(maxValue, left + right + root.val);        return Math.max(left, right) + root.val; // 子树，只能取一条叉    }