二叉树的遍历方式——迭代法

二叉树的遍历方式——迭代法 前序遍历（迭代法）中—>左—>右

前序遍历时，每次首先处理的是中间结点，那么先将根节点放入栈中，然后将右孩子加入栈，再加上左孩子。

先加入右孩子，再加入左孩子；这样出栈的时候才是中左右的顺序。

 

public List preorderTraversal(TreeNode root) {
        List res = new ArrayList<>();
        Deque stack = new linkedList();
        //Stack stack = new Stack<>();
        if (root == null) {
            return res;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            //System.out.print(node.val + " ");
            res.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return res;
    }

// 直接打印的版本
public void preorderTraversal(TreeNode root) {
        if (root == null) {
            return res;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

中序遍历（迭代法）中—>左—>右

public static List inOrder(TreeNode root) {
        Stack stack = new Stack<>();
        List res = new ArrayList<>();

        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;     // 左
            }else {
                 root = stack.pop();
                res.add(root.val);    // 中
                root = root.right;    // 右
            }

        }
        return res;
    }

后序遍历（迭代法）左—>右—>中

        将前序遍历的中左右调整为中右左，然后反转res得到左右中 即后序遍历 左-右-中；         

        入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果

// 后序迭代遍历：将前序代码的 中—>左—>右调整为中—>右—>左 然后反转res得到左—>右—>中
    public static List postOrder(TreeNode root) {
        List res = new ArrayList<>();
        Deque stack = new linkedList();
        //Stack stack = new Stack<>();
        if (root == null) {
            return res;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            //System.out.print(node.val + " ");
            res.add(node.val);
            // 在前序遍历的基础上更改了入栈顺序
            
            if (node.left != null)
                stack.push(node.left);
            if (node.right != null)
                stack.push(node.right);
        }
        Collections.reverse(res);
        return res;

    }