[数据结构与算法]二叉树遍历的非递归方法

前序遍历：

class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
public class Test02Tree {
    //不使用递归来遍历二叉树
    //前序遍历
    //首先准备一个栈，把根节点入栈，
    //①循环取栈顶元素同时入栈，并访问栈顶元素
    //②判断当前的节点的右子树是否为null，非空就入栈
    //③判断当前节点的左子树是否为null，非空就入栈
    public static void preOderByLoop(TreeNode root){
        //需要一个栈
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return;
        }
        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode top=stack.pop();

            //访问这个节点
            System.out.println(top.val);

            //把右子树和左子树分别入栈
            if(top.right!=null){
                stack.push(top.right);
            }
            if(top.left!=null){
                stack.push(top.left);
            }
        }
    }

中序遍历：

//中序遍历
    //先从root出发（还不能访问元素），向左找，路上遇到的元素入栈，移植找到左子树为null
    //到大最左侧之后，取栈顶元素同时出栈，并且访问这个元素
    //把刚才的栈顶元素的右子树作为起点，再循环往左找，路径上遇到的元素依次入栈

    public static void inOderByloop(TreeNode root){
        if(root==null){
            return;
        }

        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;

        while (true){
            while (cur!=null){//循环往左找，把路径上遇到的节点都入栈
                stack.push(cur);
                cur=cur.left;

                //如果当前栈为空，遍历结束
                if(stack.isEmpty()){
                    break;
                }

                //取栈顶元素并访问
                TreeNode top= stack.pop();
                System.out.println(" ");

                //从当前节点的右子树出发，继续刚才的过程
                cur=top.right;
            }
        }
    }

后序遍历：

//后序遍历
    //从root出发，移植往左找，遇到的非空节点入栈
    //取出栈顶元素（peak）此时栈顶元素是否能访问，进一步判断
    //如果栈顶元素没有右子树，说明该节点可以访问，如果栈顶元素已经访问过（看上一个访问的是不是右子树）
    //如果栈顶元素不符合刚才的要求，就继续从该节点右子树出发
    //如果某个节点存在右子树，这个节点会在栈顶出现两次，
    //第一次的时候，还没有访问右子树，第二次已经访问右子树，后序遍历中某个节点的前一个元素就是该节点右子树的根节点

    public static void postOrder(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();

        TreeNode cur=root;
        //prev记录已经访问过上一个节点
        TreeNode prev=null;

        while (true){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            if(stack.isEmpty()){
                break;
            }

            //拿出栈顶元素的值，看能否访问
            TreeNode top=stack.peek();
            if(top.right==null||prev==top.right){
                //此时这个栈顶元素可以被访问
                System.out.println(top.val+" ");
                stack.pop();
                prev=top;//prev指向已经遍历完元素的最后一个
            }else {
                cur=top.right;
            }
        }
    }