java - 非递归后序遍历代码，请问bug出在哪里？

Question

java    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)
请问代码哪里出错了？

Answer 1

按你的用例 在纸上走了一遍, 逻辑应该没有错. 有一个bug:

在node 14 处理后, 栈里只有 10 一个元素了, current 为null; 接着一个循环,

current = stack.pop();

为10, 栈为空.
所以下面的code应该是:

if(current.rightchild!=null && !stack.isEmpty() && current.rightchild == stack.peek() ){

Answer 2

见正确回复