首页 > 代码库 > 二叉树的最大路径和

二叉树的最大路径和

http://www.lintcode.com/zh-cn/problem/binary-tree-maximum-path-sum/#

注意点:  root == null ,return Integer.MIN_VALUE  就说明为了一定排除这个结点,将这个结点值设为最小值,也说明路径中是至少包含一个结点的。

      最后结果一定得至少包含一个结点,不然maxPathSum也不包含结点,如果树中val都是负数,会返回0,而实际上应该返回树中的最大的负数。

      -3

            -2      -1        要返回-1而不是0.

//根节点到任一节点的单一路径最大值
private int maxSinglePathSum(TreeNode root) {
if(root == null) return 0;   
int left = maxSinglePathSum(root.left);
int right = maxSinglePathSum(root.right);
return Math.max(Math.max(left,right),0) + root.val;
}

包不包含结点的差别在    null时的return和 singleMax, sumMax的选择上,看答案吧还是,逻辑更清楚点。

http://www.jiuzhang.com/solutions/binary-tree-maximum-path-sum/

//singleMax 包含至少一个结点,maxPathSum必须包含至少一个结点。

技术分享
 1 class ResultType {
 2        int singleMax;
 3        int sumMax;
 4        public ResultType(int singleMax, int sumMax){
 5            this.singleMax = singleMax;
 6            this.sumMax = sumMax;
 7        }
 8    }
 9    private ResultType helper(TreeNode root) {
10        if(root == null) return new ResultType(Integer.MIN_VALUE, Integer.MIN_VALUE); //如果当前结点为null,怎么都不会选这个结点加入结果行列,
11                                                                      //所以一会取Max()筛选时,为了保证这个结点被筛除,设为
12                                                                      // Integer.MIN_VALUE。此处也说明,sumMax至少包含一个结点。
13         ResultType left = helper(root.left);
14         ResultType right = helper(root.right);
15         int singleMax = Math.max(Math.max(left.singleMax,right.singleMax),0) + root.val;
16         int sumMax = Math.max(Math.max(left.sumMax,right.sumMax),Math.max(0,left.singleMax) + Math.max(0,right.singleMax) + root.val);
17         return new ResultType(singleMax, sumMax);
18    }
19  public int maxPathSum(TreeNode root) {
20      return helper(root).sumMax;
21  }
View Code

 //singleMax 可以不包含结点

技术分享
 1 class ResultType {
 2        int singleMax;
 3        int sumMax;
 4        public ResultType(int singleMax, int sumMax){
 5            this.singleMax = singleMax;
 6            this.sumMax = sumMax;
 7        }
 8    }
 9    private ResultType helper(TreeNode root) {
10        //差别1
11        if(root == null) return new ResultType(0, Integer.MIN_VALUE);  
12        
13         ResultType left = helper(root.left);
14         ResultType right = helper(root.right);
15         int singleMax = Math.max(Math.max(left.singleMax,right.singleMax),0) + root.val;
16         //差别3  这一行可有可无,其实前面的约束已经足够了,所以这一行没必要写,写了也不影响,只是多余操作而已。
17         singleMax = Math.max(singleMax, 0);
18         
19         //差别2
20         int sumMax = Math.max(Math.max(left.sumMax,right.sumMax),Math.max(0,left.singleMax) + Math.max(0,right.singleMax) + root.val);
21         
22         return new ResultType(singleMax, sumMax);
23    }
24  public int maxPathSum(TreeNode root) {
25      return helper(root).sumMax;
26  }
27  
View Code

 

二叉树的最大路径和