5-前、中、后序遍历的非递归算法

0.思路

前、中、后序的非递归算法都是借助栈来完成的

1.前序遍历非递归

144. 二叉树的前序遍历
遍历顺序：中、左、右
思路：从根节点开始将所有的左孩子加入栈中，将一个节点入栈时就visit该节点

    // 前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> res = new LinkedList<>();
        TreeNode p = root;
        while(p!=null || stack.size()>0){
            // 从根节点开始,一直向左将左孩子入栈
            while(p!=null){
                res.add(p.val);
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            p = p.right;
        }
        return res;
    }

2.中序遍历非递归

94. 二叉树的中序遍历
遍历顺序：左、中、右
思路：从根节点开始将所有的左孩子加入栈中，出栈时才visit该节点

    // 中序遍历,出栈时才访问node
    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> res = new LinkedList<>();
        TreeNode p = root;
        while(p!=null || stack.size()>0){
            // 从根节点开始,一直向左将左孩子入栈
            while(p!=null){
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            res.add(p.val);
            p = p.right;
        }
        return res;
    }

3.后序遍历非递归

145. 二叉树的后序遍历
遍历顺序：左、右、中
思路：中、右、左的逆序就是左、右、中，所以从根节点开始将所有的右孩子加入栈中，入栈时就visit该节点，结果集reverse后就是答案

    // 后序遍历,入栈时就visit该节点,结果集要reverse才是答案
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> res = new LinkedList<>();
        TreeNode p = root;
        while(p!=null || stack.size()>0){
            // 从根节点开始,一直向右将右孩子入栈
            while(p!=null){
                res.add(p.val);
                stack.push(p);
                p = p.right;
            }
            p = stack.pop();
            p = p.left;
        }
        Collections.reverse(res);
        return res;
    }