public static void postOrderNonrecur(Treenode rootnode){
if(rootnode==null){
return;
}
Stack<Treenode> stack = new Stack<Treenode>();
Treenode current = rootnode;
while(current !=null || stack.isEmpty()!=true){
//step 1
while(current!=null){
if(current.rightchild!=null){
stack.push(current.rightchild);
}
stack.push(current);
current = current.leftchild;
}
current = stack.pop();
if(current.rightchild!=null && current.rightchild == stack.peek() ){
System.out.println("here");
stack.pop(); //出栈右孩子
stack.push(current);
current = current.rightchild;
}
else{
System.out.println(current.value);
current = null;
}
}
}
测试用例是
出错是:
Exception in thread "main" 4
7
8
6
12
16
14
java.util.EmptyStackException
at java.util.Stack.peek(Unknown Source)
at gsm.Tree.postOrderNonrecur(Tree.java:110)
at gsm.Tree.main(Tree.java:140)
请问代码哪里出错了?
按你的用例 在纸上走了一遍, 逻辑应该没有错. 有一个bug:
在node 14 处理后, 栈里只有 10 一个元素了, current 为null; 接着一个循环,
current = stack.pop();
为10, 栈为空.
所以下面的code应该是:if(current.rightchild!=null && !stack.isEmpty() && current.rightchild == stack.peek() ){
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。