二叉树的前/中/后序遍历——迭代法

二叉树的前/中/后序遍历用递归方式非常容易实现，也较为容易理解，而采用迭代方式实现就更为复杂一些。

前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        // 迭代（根左右）
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if(root==null){
            return result;
        }
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode temp = stack.pop();
            result.add(temp.val);
            // 栈：先进后出，因此先把右加入，再把左加入
            if(temp.right!=null){
                stack.push(temp.right);
            }
            if(temp.left!=null){
                stack.push(temp.left);
            }
        }
        return result;
    }
}

中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // 迭代：左根右
        List<Integer> result = new ArrayList<>();
        if(root==null){
            return result;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        
        while(!stack.isEmpty() || cur!=null){
            // 处理左
            while(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            result.add(cur.val);
            // 处理右
            cur = cur.right;
        }
        return result;
    }
}

后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        // 迭代法思路，先根右左，然后倒序即可
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if(root==null){
            return result;
        }
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode temp = stack.pop();
            result.add(temp.val);

            if(temp.left!=null){
                stack.push(temp.left);
            }
            if(temp.right!=null){
                stack.push(temp.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}