r**h
发帖数: 1288 | 1 直接使用st.push(cur->left);将左子树节点入栈
和先赋值cur = cur->left; 再st.push(cur);
结果竟然是不一样的
找了半天找不到bug，结果简单替换一下就正常了- -!
真心请教一下，这是为什么呀。。。 |
p****e
发帖数: 3548 | |
r**h
发帖数: 1288 | 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**h
发帖数: 1288 | 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****e
发帖数: 3548 | 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**h
发帖数: 1288 | 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的值，结果就不一样了。。
|
L********e
发帖数: 159 | 7 替换前后cur的值不一样呀，一个是cur另一个是cur->left
【在 r**h 的大作中提到】
: 但是我就是直接替换的呀
: 将
: if(cur->left != NULL){
: cur = cur->left;
: st.push(cur);
: }
: 换成
: if(cur->left != NULL){
: st.push(cur->left);
: }
|
r**h
发帖数: 1288 | 8 哦哦。。。突然理解了！！
是因为cur值改变导致后面prev得不到正确的值了
哎我真粗心
【在 L********e 的大作中提到】
: 替换前后cur的值不一样呀，一个是cur另一个是cur->left
|
