前几天在知乎看到一个关于非递归遍历二叉树的问题。
就试着自己尝试了一下。

因为递归本身也是利用函数的调用栈，只是通过参数来控制你当前访问的是左节点还是右节点，所以更容易理解。

前序遍历:

	public void TraversalTree(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode n = node;
        while (!stack.isEmpty() || n != null) {
            while (n != null) {
                System.out.println(n.value);
                stack.push(n);
                n = n.left;
            }
            n = stack.pop();
            n = n.right;
        }
    }

中序遍历:

public void TraversalTree2(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode n = node;
        while (!stack.isEmpty() || n != null) {
            if (n != null) {
                stack.push(n);
                n = n.left;
            } else {
                n = stack.pop();
                System.out.println(n.value);
                n = n.right;
            }
        }
    }

后序遍历应该是最难的。，最主要的是要判断一个节点的右子树有没有被访问过。所以得有一个last记录上一次的位置。每次对于每一个子树，都要先到达最左边。
真的挺麻烦

public void TraversalTree3(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode n = node;
        TreeNode last = node;
        while (!stack.isEmpty() || n != null) {
            //到达最左边
            if (n != null) {
                stack.push(n);
                n = n.left;
            } else {
                //获取栈顶
                n = stack.peek();
                //如果此时的右子树没有访问过，则访问右子树
                if (n.right != null && last != n.right) {
                    n = n.right;
                } else {
                    stack.pop();
                    System.out.println(n.value);
                    last = n;
                    n = null;
                }
            }
        }
    }