遇到了一个很奇怪的C++问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

遇到了一个很奇怪的C++问题

遇到了一个很奇怪的C++问题# JobHunting - 待字闺中

r*h2013-06-29 07:06

1 楼

直接使用st.push(cur->left);将左子树节点入栈
和先赋值cur = cur->left; 再st.push(cur);
结果竟然是不一样的
找了半天找不到bug，结果简单替换一下就正常了- -!
真心请教一下，这是为什么呀。。。

p*e2013-06-29 07:06

2 楼

全部code贴出来看看

r*h2013-06-29 07:06

3 楼

就是循环后序遍历呀
if(prev==NULL || prev->left==cur || prev->right==cur){
if(cur->left != NULL){
st.push(cur->left); <==============
}
else if(cur->right != NULL){
st.push(cur->right); <==============
}
}
大概像这样
箭头指着的地方换成一开始的写法就不行了

【在 p****e 的大作中提到】

: 全部code贴出来看看

r*h2013-06-29 07:06

4 楼

class Solution {
public:
int maxDepth(TreeNode *root) {
if(root == NULL) return 0;
stack st;
st.push(root);
TreeNode *prev=NULL, *cur;
int maxHeight = 0;

while(st.size()>0){
cur = st.top();
if(prev==NULL || prev->left==cur || prev->right==cur){
if(cur->left != NULL){
st.push(cur->left);
}
else if(cur->right != NULL){
st.push(cur->right);
}
}
else if(cur->left == prev){
if(cur->right != NULL){
st.push(cur->right);
}
}
else{
st.pop();
}
if(st.size() > maxHeight){
maxHeight = st.size();
}
prev = cur;
}
return maxHeight;
}
};
完整代码是这样的

p*e2013-06-29 07:06

5 楼

当然不对了，后面你有
prev = cur;
如果你修改了cur的值，结果就不一样了。。

【在 r**h 的大作中提到】

: class Solution {
: public:
: int maxDepth(TreeNode *root) {
: if(root == NULL) return 0;
: stack st;
: st.push(root);
: TreeNode *prev=NULL, *cur;
: int maxHeight = 0;
:
: while(st.size()>0){

r*h2013-06-29 07:06

6 楼

但是我就是直接替换的呀
将
if(cur->left != NULL){
cur = cur->left;
st.push(cur);
}
换成
if(cur->left != NULL){
st.push(cur->left);
}
应该不存在cur的值被改变的问题吧？

【在 p****e 的大作中提到】

: 当然不对了，后面你有
: prev = cur;
: 如果你修改了cur的值，结果就不一样了。。