JobHunting版 - leetcode中的binary tree level order traverse II总是有run t |
|---|
|
|
|
|
|
|
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;
|
|
|
|
|
|
|
|
