l********t
发帖数: 878 | 1 Judge small 全对
Judge large, 一共92个test case,有90个是对滴，
其中一个错误的是这个test case
{9,6,-3,#,#,-6,2,#,#,2,#,-6,-6,-6}
还有一个太长，不写了。
我自己编译运行结果是16，也是正确答案。上OJ非说我的结果是15...
leetcode，或者哪位大牛给看看？谢谢啊！
/**
* Definition for binary tree */
#include
#include
#include
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxValue;
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int singleDown;
maxValue = -9999;
return maxPathOverload(root, singleDown);
}
int maxPathOverload(TreeNode* root, int& singleLine){
if (!root){
singleLine = 0;
return 0;
}
int leftSingleLine = 0;
int rightSingleLine = 0;
maxPathOverload(root->left, leftSingleLine);
maxPathOverload(root->right, rightSingleLine);
singleLine = root->val + max(leftSingleLine , rightSingleLine);
vector subMaxPath;
subMaxPath.push_back(root->val);
subMaxPath.push_back(root->val + leftSingleLine);
subMaxPath.push_back(root->val + rightSingleLine);
subMaxPath.push_back(root->val + leftSingleLine + rightSingleLine);
maxValue = max(maxValue, *max_element(subMaxPath.begin(), subMaxPath
.end()));
//compare the path values, which you HAVE TO include the current
node
//This eleminate the zero's for null leaf's
return maxValue;
}
};
//{9,6,-3,#,#,-6,2,#,#,2,#,-6,-6,-6}
int main(){
TreeNode n1(9);
TreeNode n1L(6);
TreeNode n1R(-3);
TreeNode n2L(-6);
TreeNode n2R(2);
TreeNode n3L(2);
TreeNode n4L(-6);
TreeNode n4R(-6);
TreeNode n5L(-6);
n1.left = &n1L;
n1.right = &n1R;
n1R.left = &n2L;
n1R.right = &n2R;
n2R.left = &n3L;
n3L.left = &n4L;
n4L.right = &n4R;
n4R.left = &n5L;
Solution s;
int result = 0;
result = s.maxPathSum(&n1);
cout<
} | l*********8
发帖数: 4642 | 2 This is the reason?
IMPORTANT:
The Solution object is instantiated only once and is reused for each
test case input. When declaring a class member variable, be extra cautious
and remember to reset the variable!
【在 l********t 的大作中提到】
: Judge small 全对
: Judge large, 一共92个test case,有90个是对滴，
: 其中一个错误的是这个test case
: {9,6,-3,#,#,-6,2,#,#,2,#,-6,-6,-6}
: 还有一个太长，不写了。
: 我自己编译运行结果是16，也是正确答案。上OJ非说我的结果是15...
: leetcode，或者哪位大牛给看看？谢谢啊！
: /**
: * Definition for binary tree */
: #include
| l********t
发帖数: 878 | 3 这个我留心了，不过好像不是啊。
each
【在 l*********8 的大作中提到】
: This is the reason?
: IMPORTANT:
: The Solution object is instantiated only once and is reused for each
: test case input. When declaring a class member variable, be extra cautious
: and remember to reset the variable!
| l*********8
发帖数: 4642 | 4 好像跟我以前发现的bug是一样的。
singleLine = root->val + max(leftSingleLine , rightSingleLine);
改成
singleLine = max(0, root->val + max(leftSingleLine , rightSingleLine));
【在 l********t 的大作中提到】
: 这个我留心了，不过好像不是啊。
:
: each
| i**********e
发帖数: 1145 | 5 你的输入出了个小问题，应该是：
n3L.right = &n4R;
n4L.left = &n5L;
这样运行你的程序就会 output 15。
【在 l********t 的大作中提到】
: Judge small 全对
: Judge large, 一共92个test case,有90个是对滴，
: 其中一个错误的是这个test case
: {9,6,-3,#,#,-6,2,#,#,2,#,-6,-6,-6}
: 还有一个太长，不写了。
: 我自己编译运行结果是16，也是正确答案。上OJ非说我的结果是15...
: leetcode，或者哪位大牛给看看？谢谢啊！
: /**
: * Definition for binary tree */
: #include
| l********t
发帖数: 878 | 6 谢谢大牛火眼金睛！
【在 i**********e 的大作中提到】
: 你的输入出了个小问题，应该是：
: n3L.right = &n4R;
: n4L.left = &n5L;
: 这样运行你的程序就会 output 15。
| l********t
发帖数: 878 | 7 另外谢谢 longway2008，确实是算单线最长的时候没考虑周到。贴个改过后work的
class Solution {
public:
int maxValue;
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int singleDown;
maxValue = -9999;
return maxPathOverload(root, singleDown);
}
int maxPathOverload(TreeNode* root, int& singleLine){
if (!root){
singleLine = 0;
return 0;
}
int leftSingleLine = 0;
int rightSingleLine = 0;
maxPathOverload(root->left, leftSingleLine);
maxPathOverload(root->right, rightSingleLine);
vector subMaxPath;
subMaxPath.push_back(root->val);
subMaxPath.push_back(root->val + leftSingleLine);
subMaxPath.push_back(root->val + rightSingleLine);
singleLine = *max_element(subMaxPath.begin(), subMaxPath.end());
subMaxPath.push_back(root->val + leftSingleLine + rightSingleLine);
maxValue = max(maxValue, *max_element(subMaxPath.begin(), subMaxPath
.end()));
//compare the path values, which you HAVE TO include the current
node
//This eleminate the zero's for null leaf's
return maxValue;
}
}; |
|
