首页 > 其他 > 详细

Leetcode | Binary Tree Maximum Path Sum

时间:2014-05-07 09:35:52      阅读:469      评论:0      收藏:0      [点我收藏+]

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

1
/ \
2 3
Return 6.

最大值是以下几种情况的最大值:

1. 左子树的最大值;

2. 右子树的最大值;

3. 部分path在左子树,部分path在右子树,经过root;

1和2很多计算,在递归中保持就行,这里用maxDouble表示(两边都有);

3的话需要维护止于root点的最大值,这里用maxSingle表示(只有一边,止于root);

初始值的话不能设成0、-1之类的某个数,因为这些数可能出现,也可能不出现,因为是最大值比较,所以用INT_MIN;

bubuko.com,布布扣
 1 class Solution {
 2 public:
 3     int maxPathSum(TreeNode *root) {
 4         int maxDouble = INT_MIN, maxSingle = INT_MIN;
 5         recursive(root, maxDouble, maxSingle);
 6         return maxDouble;
 7     }
 8     
 9     void recursive(TreeNode* root, int &maxDouble, int &maxSingle) {
10         if (root == NULL) return;
11         int v1, v2, v3, v4;
12         v1 = v2 = v3 = v4 = INT_MIN;
13         recursive(root->left, v1, v2);
14         recursive(root->right, v3, v4);
15         maxSingle = v2 > v4 ? v2 : v4;
16         if (maxSingle < 0) maxSingle = root->val;
17         else maxSingle += root->val;
18         
19         maxDouble = maxSingle; 
20         if (v1 > maxDouble) maxDouble = v1;
21         if (v3 > maxDouble) maxDouble = v3;
22         if (v2 != INT_MIN && v4 != INT_MIN && v2 + v4 + root->val > maxDouble) maxDouble = v2 + v4 + root->val;
23     }
24 };
bubuko.com,布布扣

maxSingle很好求,可以先求左右maxSingle的最大值,如果这个值是正数,那么可以把root也算上,不然就直接是root了。

maxDouble至少是maxSingle,然后再和左右子树的maxDouble比,最后和经过root,包含左右子树的情况相比。注意的是排除掉左右子树为空的情况。

Cheers!庆祝Leetcode终于刷了100题。44天,当然中间大部分时间是要忙实验室的活,还有放假出去玩的时间,真正在做的时间一般多。

Leetcode | Binary Tree Maximum Path Sum,布布扣,bubuko.com

Leetcode | Binary Tree Maximum Path Sum

原文:http://www.cnblogs.com/linyx/p/3710484.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!