二叉树的遍历非递归算法

一.先序遍历

二叉树的先序遍历其实就是深度遍历，如图所示：

用栈来实现。

首先是将所有节点的左子树的元素全部都进栈，退出循环之后，先访问树的最左边的一个节点，也就是栈顶元素，并将它pop，然后将其右子树入栈。

public ArrayList preorderTraversal(TreeNode root) {
       ArrayList list = new ArrayList();
        if(root == null)return list;
        Stack S = new Stack();
        TreeNode p = root;
        while(p != null || !S.empty()){
        while(p != null){
        S.push(p);
        list.add(p.val);
        p = p.left;
        }
    p = S.pop();
    p = p.right;
    }
    return list;
    }

二.中序遍历

用栈来实现。它与先序遍历的区别是，先序是入栈的时候访问节点的value，而中序遍历是出栈的时候，访问节点的value

public ArrayList inorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if(root == null)return list;
        Stack S = new Stack();
        TreeNode p = root;
        while(p!=null || !S.empty()){
            while(p!=null){
                S.push(p);  
                p = p.left;
            }
            p = S.pop();
            list.add(p.val);
            p = p.right;  
        }
        return list;
    }

三.后序遍历

后序遍历是非递归遍历算法中最难理解的。它需要设置一个标记位，表明这棵子树已访问过。