二叉树后序遍历非递归遍历实现图解

二叉树的后序遍历

输入：

{1,#,2,3}

返回值：

[3,2,1]

输入：

{1}

返回值：

[1]

代码实现

      public int[] postorderTraversal (TreeNode root) {
            TreeNode cur = root;
            List<Integer> list = new ArrayList<>();
            Deque<TreeNode> stack = new ArrayDeque<>();
             TreeNode pre = null;
            while(!stack.isEmpty() || cur != null) {
                while(cur != null){
                    stack.push(cur);
                    cur = cur.left;
                }
               
                TreeNode top = stack.pop();
                if(top.right == null || top.right == pre) {
                    list.add(top.val);
                    pre = top;
                } else {
                    stack.push(top);
                    cur = top.right;
                }
            }
            int [] arr = new int[list.size()];
            for(int i = 0; i < list.size(); i++) {
                arr[i] = list.get(i);
            }
            return arr;
        }

图解

发现bug

我们就可以添加一个判断标志防止出现死循环