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

• Z时代
• 2024-01-10
• 分类：IT

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)

请问代码哪里出错了？

回答：

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

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

current = stack.pop();

为10, 栈为空.

所以下面的code应该是:

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

回答：

见正确回复

以上是 非递归后序遍历代码，请问bug出在哪里？ 的全部内容， 来源链接： utcz.com/p/180917.html