#题目： 用非递归的方式写一下二叉树的遍历 分别包含前序遍历 中序遍历 和 后序遍历

谢谢阿毛同学，他对这三个遍历理解比较深刻

#method 1 先写 前序遍历 理解起来较容易

//这个非递归版本的前序遍历很容易理解

    public void preOrderTravelse(TreeNode root){
        if(root == null){
            return;
        }
        Stack<TreeNode> sta = new Stack<>();
        sta.push(root);
        while(sta.size()>0){
            TreeNode cur = sta.peek();
            sta.pop();
            System.out.print(cur.val+"  ");
            if(cur.right != null){
                sta.push(cur.right);
            }
            if(cur.left != null){
                sta.push(cur.left);
            }
        }
    }

#method 2 中序遍历 结合注释看看，理解起来很轻松

//这个非递归版本的中序遍历也需要好好理解

    public void inOrderTravelse(TreeNode root){
        if(root == null){
            return;
        }
        Stack<TreeNode> sta = new Stack<>();
        TreeNode p = root;
        while(p !=null || sta.size()>0){  //p是指我们要压入栈中的节点    只看左子树

            while(p!=null){
                sta.push(p);
                p = p.left;
            }   //这个结束后  p = null

            
            if(sta.size()>0){  //cur是指我们要弹出栈的节点       只看右子树

                TreeNode cur = sta.pop();
                System.out.print(cur.val+"  ");
                if(cur.right != null){
                    p = cur.right;
                }
            }
        }
    }

#method 3
最后这个非递归的后序遍历版本是我见过最容易理解的。。。。。。

//这个非递归版本的后序遍历简直不要太简单

    public void postOrderTravelse(TreeNode root){
        if(root == null){
            return;
        }
        Stack<TreeNode> sta = new Stack<>();
        sta.push(root);
        while(sta.size()>0){
            TreeNode cur = sta.peek();
            if(cur.left==null && cur.right==null){
                System.out.print(cur.val+"  ");
                sta.pop();
            }
            if(cur.right !=null){
                sta.push(cur.right);
                cur.right = null;
            }
            if(cur.left != null){
                sta.push(cur.left);
                cur.left = null;
            }
        }
    }