由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - leetcode中的binary tree level order traverse II总是有run t
相关主题
请教一道Leetcode 题,多谢我又fail了面试
相关话题的讨论汇总
话题: treenode话题: vector话题: tag话题: back话题: allpath
进入JobHunting版参与讨论
1 (共1页)
b*******n
发帖数: 847
1
如题,我想实现先把整个tree breadth-first traverse,traverse结果放在vector里
(vector allPath)
,每层遍历到了最后加一个tag node,最后把vector从后往前scan。想法很简单,但
code总是有错。我对vector不熟,估计是member function没用对,请大家帮忙看看,
多谢了!
vector > levelOrderBottom(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > traversal;
vector allPath;
if(!root) return traversal;
TreeNode *tag=new TreeNode(0);
allPath.push_back(root);
allPath.push_back(tag);
std::vector::iterator begin=allPath.begin();
std::vector::iterator end=allPath.end();
std::vector::iterator it=begin;
while(it if(*it==tag)
allPath.push_back(tag);
else{
if((*it)->left)
allPath.push_back((*it)->left);
if((*it)->right)
allPath.push_back((*it)->right);
}
it++;
end=allPath.end();
}
......
run time error就在这个while循环里,用allPath.push_back() 来push left 或right
child时总是不对,感觉push进去的不是指针。卡在这儿好久了,想不出为什么,希望
大家指点,谢谢!!
d**e
发帖数: 6098
2

不知我有没有理解错,我觉得这个if有可能导致死循环。
比如是
1
/ \
2 3
开始时allPath: 1, tag
it指向1时,allPath: 1, tag, 2, 3
it指向tag时,allPath: 1, tag, 2, 3, tag
it指向2,3时不变,仍是allPath: 1, tag, 2, 3, tag
it指向最后一个tag时,加一个tag,allPath: 1, tag, 2, 3, tag, tag
再指下一个tag,再加一个tag,继续指到下一个tag。。。
right

【在 b*******n 的大作中提到】
: 如题,我想实现先把整个tree breadth-first traverse,traverse结果放在vector里
: (vector allPath)
: ,每层遍历到了最后加一个tag node,最后把vector从后往前scan。想法很简单,但
: code总是有错。我对vector不熟,估计是member function没用对,请大家帮忙看看,
: 多谢了!
: vector > levelOrderBottom(TreeNode *root) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: vector > traversal;
: vector allPath;

p*****p
发帖数: 379
3
你的iterator是while外赋值的,但每次push_back都会invalidate那个begin,再操作
iterator的话结果是不可知的

【在 b*******n 的大作中提到】
: 如题,我想实现先把整个tree breadth-first traverse,traverse结果放在vector里
: (vector allPath)
: ,每层遍历到了最后加一个tag node,最后把vector从后往前scan。想法很简单,但
: code总是有错。我对vector不熟,估计是member function没用对,请大家帮忙看看,
: 多谢了!
: vector > levelOrderBottom(TreeNode *root) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: vector > traversal;
: vector allPath;

p*****p
发帖数: 379
4
刚写了个,可以过
class Solution {
public:
vector > levelOrderBottom(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
deque > traversal;
vector > ret;
if(!root) return ret;
vector q1;
vector q2;
q1.push_back(root);

while (!q1.empty() || !q2.empty()) {
if (!q1.empty()) {
vector row;
for (auto node : q1) {
row.push_back(node->val);
if (node->left) q2.push_back(node->left);
if (node->right) q2.push_back(node->right);
}
traversal.push_front(row);
q1.clear();
}
else {
vector row;
for (auto node : q2) {
row.push_back(node->val);
if (node->left) q1.push_back(node->left);
if (node->right) q1.push_back(node->right);
}
traversal.push_front(row);
q2.clear();
}
}

for (auto row : traversal) {
ret.push_back(row);
}

return ret;
}
};
b*******n
发帖数: 847
5
这个应该没有问题,因为iterator只扫到倒数第二个值,不会扫最后一个tag,不过谢
谢讨论啊 ^_^

★ 发自iPhone App: ChineseWeb 7.8

【在 d**e 的大作中提到】
:
: 不知我有没有理解错,我觉得这个if有可能导致死循环。
: 比如是
: 1
: / \
: 2 3
: 开始时allPath: 1, tag
: it指向1时,allPath: 1, tag, 2, 3
: it指向tag时,allPath: 1, tag, 2, 3, tag
: it指向2,3时不变,仍是allPath: 1, tag, 2, 3, tag

b*******n
发帖数: 847
6
原来是这样!在debug时我也发现end会变的很离谱,不是仅仅加几个byte的那种,但没
想到这点。也就是说每次push_back都
新建一个dynamic vector重新赋值然后把老的删掉么?看来得回去看看source code啊
。。多谢指点!

【在 p*****p 的大作中提到】
: 你的iterator是while外赋值的,但每次push_back都会invalidate那个begin,再操作
: iterator的话结果是不可知的

b*******n
发帖数: 847
7
谢谢!
经过你提醒我改了我的code,这回过了,发现用array的index来referecen简单多了
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector > levelOrderBottom(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > traversal;
vector path;
vector allPath;
if(!root) return traversal;
TreeNode *tag=new TreeNode(0);
allPath.push_back(root);
allPath.push_back(tag);
int index=0;
while(index TreeNode* t=allPath[index];
if(t==tag)
allPath.push_back(tag);
else{
if(t->left)
allPath.push_back(t->left);
if(t->right)
allPath.push_back(t->right);
}
index++;
}
int end=allPath.size()-1;
int begin=end-1;
index=begin;
while(begin){
while(begin&&allPath[begin]!=tag) begin--;
if(allPath[begin]==tag) index=begin+1;
else index=begin;
for (;index path.push_back(allPath[index]->val);
traversal.push_back(path);
path.clear();
if(allPath[begin]==tag){
end=begin;
begin--;
}
}
path.push_back(allPath[begin]->val);
traversal.push_back(path);
return traversal;
}
};

【在 p*****p 的大作中提到】
: 刚写了个,可以过
: class Solution {
: public:
: vector > levelOrderBottom(TreeNode *root) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: deque > traversal;
: vector > ret;
: if(!root) return ret;
: vector q1;

1 (共1页)
进入JobHunting版参与讨论
相关主题
请教一道Leetcode 题,多谢我又fail了面试
相关话题的讨论汇总
话题: treenode话题: vector话题: tag话题: back话题: allpath