Java二叉树非递归实现

 //前序遍历
    /**
     * 根-左-右，所以入栈的时候要相反，有右节点则加入右节点，有左节点则加入左节点，每车循环的时候，弹一个
     */
    public ArrayList preorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        Stack stack = new Stack();
        if (root == null){
            return list;
        }
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode temp = stack.pop();
            list.add(temp.val);
            if (temp.right!=null){
                stack.push(temp.right);
            }
            if (temp.left!=null){
                stack.push(temp.left);
            }
        }
        return list;
    }

 // 中序遍历 非递归算法
    public static void InOrder2(TreeNode root) {
        if(root==null)return;
        Stack stk = new Stack();
        TreeNode p = root;//辅助节点
        stk.add(p);
        while(stk.isEmpty() == false) {
            //只要你有左孩子，就将左孩子压入栈中
            if(p!=null &&  p.left!=null) {
                stk.add(p.left);
                p = p.left;
            }else {
                p = stk.pop();//弹出栈顶节点  左孩子--->根节点
                System.out.print(p.val+" ");//访问
                if(p!=null && p.right!=null) {//如果栈点元素有右孩子的话，将有节点压入栈中
                    stk.add(p.right);
                    p = p.right;
                }else
                    p = null;//p=stk.pop;已经访问过p了，p设置为null
            }
        }
    }

  /**
     * 后序遍历
     */
    public static void postOrderFast(TreeNode root) {
        if (root == null) {
            return;
        }

        Stack s1 = new Stack();
        Stack s2 = new Stack();

        s1.push(root);

        TreeNode curNode;
        while(!s1.isEmpty()) {

            curNode = s1.pop();
            // 中、右、左顺序压入栈中
            s2.push(curNode);

            // 压入s1为先左后右，保证中、右、左顺序压入s2中
            if (curNode.left != null) {
                s1.push(curNode.left);
            }
            if (curNode.right != null) {
                s1.push(curNode.right);
            }
        }

        while (!s2.isEmpty()) {
            System.out.print(s2.pop().val + " ");
        }
    }