虽说递归是二叉树的灵魂，但还是非常推荐掌握非递归实现前中后序遍历的

以下三种非递归实现，我们都需要借助栈（Stack）后进先出的特性

一、preOrder

思路：

借助stack存放二叉树中的节点类型TreeNode

想一想前序遍历是怎么打印的，我们原通过递归，一路往根节点的left走，碰到节点就打印其中的值，当来到最左下角时，也就是说无法继续向左时，递归开始回退，转而开始去遍历这个节点的右子树，如果右子树的左不为空，则继续一路往left走，无法向左，递归又回退

非递归思路：

借助栈的后进先出原则，我们一路向left时，打印路上节点的同时收集(push)一下这些节点，当无法向左时，我们发现，stack.pop()出来的节点正好就是最左下角的节点，此时我们转而去检查这个节点的右子树，利用相同的规则，收集...打印...发现无法向左，检查并遍历该节点的右子树...收集...打印......

代码实现：

@Override
public void preOrder2(IBinarryTree.TreeNode root) {
   if(root==null){
       return;
   }

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

   while(cur!=null||!stack.isEmpty()){
       while(cur!=null){
           stack.push(cur);
           System.out.print(cur.val+" ");
           cur = cur.left;
       }
       IBinarryTree.TreeNode top = stack.pop();
       cur = top.right;
   }
}

二、inOrder

思路：

联想一下，我们在递归实现中序遍历时，路上碰到某个节点，要先检查这个节点的左是否为空，如果为空才能打印这个节点的值，如果不为空，则继续向left走，当无法向left走时，说明这个节点已经没有左孩子了，此时该节点符合我们中序遍历的打印条件，当无法向left走时，此时转而去检查遍历该节点的右子树，依旧同样的规则

非递归实现思路：

借助stack，和前序遍历很相似，不过，我们一路向left走并收集节点的时候，不要再立马打印了，应该先检查这个节点是否还有左子树，如果没有才打印，然后我们转而去遍历该节点的右子树

代码实现：

@Override
public void inOrder2(IBinarryTree.TreeNode root) {
   if(root==null){
       return;
   }
   Stack<IBinarryTree.TreeNode> stack = new Stack<>();
   IBinarryTree.TreeNode cur = root;

   while(cur!=null||!stack.isEmpty()){
       while(cur!=null){
           stack.push(cur);
           cur = cur.left;
       }
       IBinarryTree.TreeNode top = stack.pop();
       System.out.print(top.val+" ");
       cur = top.right;
   }
}

三、postOrder

思路：

再次联想递归实现时的思路，我们在一路往left的时候，碰到节点，需要检查该节点是否左右孩子都被打印过了，或者都为null，我们才能打印该节点的值

非递归实现思路：

借助stack，一路向left走并收集路上的节点，当无法再向left走时，说明此时栈顶元素的左一定为null，我们peek一下这个栈顶元素，检查其是否存在右孩子，或者右孩子已经被打印过了（我们定义一个prev，用来标记某个节点的右孩子是否被打印过），此时我们可以打印这个节点的值

代码实现：

@Override
public void postOrder2(IBinarryTree.TreeNode root) {
     if(root==null){
         return;
     }
     Stack<IBinarryTree.TreeNode> stack = new Stack<>();

    IBinarryTree.TreeNode cur = root;
    IBinarryTree.TreeNode prev = null;
    while(cur!=null||!stack.isEmpty()){
        while(cur!=null){
            stack.push(cur);
            cur = cur.left;
        }
        IBinarryTree.TreeNode top = stack.peek();
        if(top.right==null||top.right==prev){
            System.out.print(top.val+" ");
            stack.pop();
            prev = top;
        }else if(top.right!=null){
            cur = top.right;
        }
    }
}