递归的函数调用就是通过栈来实现的，因此二叉树的非递归实现也可借助栈来完成

先序遍历

要按照根-左-右的顺序遍历，我们先将头结点压入栈中，只要栈不为空，就弹出一个结点并打印，然后依次压入该弹出结点的右结点和左结点。

    public static void preOrder(TreeNode head) {
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                System.out.print(head.val + " ");
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
            System.out.println();
        }
    }

中序遍历

要按照左-根-右的顺序遍历，
1）先将子树根及其左边界入栈
2）弹出栈顶结点并打印，然后对该结点的右子树重复1）
3）没子树且栈空，结束

    public static void inOrder(TreeNode head) {
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.print(head.val + " ");
                    head = head.right;
                }
            }
            System.out.println();
        }
    }

可见，只有处理完左子树和自身之后，才处理右子树，也就实现了中序遍历。

后续遍历

两个栈实现

先序遍历是按照根-左-右的顺序去实现的，我们可以修改先序遍历的方法，使其按照根-右-左来打印结点，而我们可以不打印结点，改为将其入栈，遍历完之后出栈，就可以得到左-右-根的打印顺序，也即后序遍历。

    public static void posOrderTwoStacks(TreeNode head) {
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> collect = new Stack<>();
            stack.push(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                collect.push(head);
                if (head.left != null) {
                    stack.push(head.left);
                }
                if (head.right != null) {
                    stack.push(head.right);
                }
            }
            while (!collect.isEmpty()) {
                System.out.print(collect.pop().val + " ");
            }
            System.out.println();
        }
    }

一个栈实现

首先定义一个哨兵h，初始时h指向二叉树的根结点，将h入栈。之后h指向上一次处理过的结点，弹出处理栈顶元素，
1）有左树且左树没有处理过（即h不指向左树），左树入栈；
2）有右树且右树没有处理过（即h不指向右树），右树入栈；
3）左右树为空或左右树都处理过了，打印该结点，并将h指向该结点

    public static void posOrderOneStack(TreeNode h) {
        if (h != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(h);
            // 如果始终没有打印过节点，h就一直是头节点
            // 一旦打印过节点，h就变成打印节点
            // 之后h的含义 : 上一次打印的节点
            while (!stack.isEmpty()) {
                TreeNode cur = stack.peek();
                if (cur.left != null && h != cur.left && h != cur.right) {
                    // 有左树且左树没处理过
                    stack.push(cur.left);
                } else if (cur.right != null && h != cur.right) {
                    // 有右树且右树没处理过
                    stack.push(cur.right);
                } else {
                    // 左树、右树 没有 或者 都处理过了
                    System.out.print(cur.val + " ");
                    h = stack.pop();
                }
            }
            System.out.println();
        }
    }

时间、空间复杂度分析

对于一个栈实现的先中后序遍历，由于每个结点都要入栈和出栈一次，故时间复杂度为O（n），空间复杂度为O（h），h为二叉树的树高，也就是栈的最大深度。
而两个栈实现的后序遍历，时间复杂度为O（n），由于需要收集所有结点，再从栈里弹出，因此空间复杂度为O（n）。