朕在暖脚# Joke - 肚皮舞运动
l*t
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<
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.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<
