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

二叉树的最大路径和

2024-09-20 15:55:10   218人阅读

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

 

二叉树的最大路径和


联系
我们