【二叉树打卡5】二叉树的后序遍历（非递归版）

【题目】

按照二叉树的后序遍历打印二叉树，并且不能使用递归。

【难度】

易

解答

没看过前序遍历和中序遍历的或许可以先看下：

二叉树的后序遍历顺序是左-右-根。我们可以采用一个栈来辅助，不过它和前序遍历以及中序遍历还是有点区别的，我们把后序遍历的结果放到一个 LinkedList 容器中作为返回值，具体步骤如下：

1、把二叉树的根节点 root 放进栈。

2、如果栈不为空，从栈中取出一个节点，把该节点插入到容器的头部。；如果该节点的左子树不为空，则把该左子树放入栈中；如果该节点的右子树不为空，则把右子树放入栈中。，

注意，之前的前序遍历和中序遍历，我们都是用 ArrayList 容器，并且是把节点插入到容器的尾部，这就是后序遍历的不同点。

3、一直重复步骤 2 ，直到栈为空，此时遍历结束，代码如下：

代码如下：

    // 后序遍历
    public List<Integer> postOderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();// 注意，采用链表
        Stack<TreeNode> stack = new Stack<>();
        if(root == null)
            return res;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tmp = stack.pop();
            // 注意，是放在第一个位置
            res.addFirst(tmp.val);
            if(tmp.left != null)
                stack.push(tmp.left);
            if(tmp.right != null)
                stack.push(tmp.right);

        }
        return res;
    }

往期