开发者社区> 问答> 正文

非递归后序遍历代码请问bug出在哪里?

 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;
            }
        }
    }

测试用例是
screenshot
出错是:
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)
请问代码哪里出错了?

展开
收起
蛮大人123 2016-02-28 10:34:27 1984 0
1 条回答
写回答
取消 提交回答
  • 我说我不帅他们就打我,还说我虚伪

    按你的用例 在纸上走了一遍, 逻辑应该没有错. 有一个bug:
    在node 14 处理后, 栈里只有 10 一个元素了, current 为null; 接着一个循环,
    current = stack.pop();
    为10, 栈为空.
    所以下面的code应该是:
    if(current.rightchild!=null && !stack.isEmpty() && current.rightchild == stack.peek() ){

    2019-07-17 18:49:24
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载