【二叉树的前中后序遍历】迭代法

• 三种遍历都是用栈维护二叉树前序遍历节点顺序

前序遍历

模拟前序遍历即可，记录顺序和入栈顺序一致

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null) return ans;

        Map<TreeNode, Boolean> vis = new HashMap<>();
        
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        ans.add(root.val);
        while(!s.empty()) {
            TreeNode node = s.peek();
            if(node.left != null && !vis.containsKey(node.left)) {
                s.push(node.left);
                ans.add(node.left.val);
            } else if(node.right != null && !vis.containsKey(node.right)) {
                s.push(node.right);
                ans.add(node.right.val);
            } else {
                vis.put(s.pop(), true);
            }
        }
        return ans;
    }
}

中序遍历

1. 从根开始，遍历并入栈左儿子
2. 若左儿子已被记录，先记录当前节点的value，再入栈右儿子
3. 当左右儿子都已经被记录或遍历到叶子节点，且当前节点未被记录时，记录当前节点的value，弹栈回溯到其父亲，否则直接弹栈回溯到其父亲。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null) return ans;

        Map<TreeNode, Boolean> vis = new HashMap<>();
        
        Stack<TreeNode> s = new Stack<>();
        s.push(root);

        while(!s.empty()) {
            TreeNode node = s.peek();

            if(node.left != null && !vis.containsKey(node.left)) {
                s.push(node.left);
            } else if(node.right != null && !vis.containsKey(node.right)) {
                ans.add(node.val);
                vis.put(node, true);
                s.push(node.right);
            } else if(!vis.containsKey(node)){
                ans.add(node.val);
                vis.put(s.pop(), true);
            } else {
                s.pop();
            }
        }

        return ans;

    }
}

后序遍历

1. 从根开始，遍历并入栈左儿子
2. 若左儿子已被记录，入栈右儿子；
3. 当左右儿子都已经被记录或遍历到叶子节点，则记录当前节点的value，弹栈回溯到其父亲

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null) return ans;

        Map<TreeNode, Boolean> map = new HashMap<>();
        
        Stack<TreeNode> s = new Stack<>();
        s.push(root);

        while(!s.empty()) {
            TreeNode now = s.peek();
            if(now.left != null && !map.containsKey(now.left) ) {
                s.push(now.left);
            } else if(now.right != null && !map.containsKey(now.right) ){
                s.push(now.right);
            } else {
                ans.add(now.val);
                map.put(now, true);
                s.pop();
            }
        }
        return ans;
    }
}