树的非递归前、中、后序遍历

树的递归方法是比较简单的，但是非递归方法确实比较难写和理解的。

首先说下非递归方法的前序遍历：

使用栈来记录所走过的路程，前需遍历是 根节点，左，然后一直左，走到头了，才返回走右，走完右之后还是死命的走左。通过stack记录元素的时候，是需要先记录右边再记录左边，这样弹出的元素就是每次就是最左边的。

网上有很多版本的前序、中序遍历和后序遍历的的答案，代码也不相同，逻辑很简单，实现起来就多种多样，本文就展示一个最容易记忆的递归。

前序遍历和中序遍历走的路径是一样的，都是先左，左走完了再走右边。  一个是先上后下， 一个是先下后上，先上后下的就先入栈的被记录， 如果是先下后上，自然是出栈的时候开始往上走

但两者记忆路径的方式是不一样的，一个是在入栈的时候记忆，我先嘛，我入栈的时候记忆

　　　　　　　　　　　　　　　　一个是在出栈的时候记忆，我中序，出栈记忆

if(root!=null){

　　stack.add(root);

　　root = root.left;

}else{

　　// 弹出上一个节点的值

　　root = stack.pop();

　　// 此时走右边；

　　root= root.left

}

代码如下：

后续遍历技巧：  后续遍历的内容

如果有个树结构是 [1,2,3,4,5,6,7]   其后续遍历就是 　　：4，5，2，6，7，3，1

　　　　　　　　　　　　　　　其镜像的前序遍历为 ：1，3，7，6，2，5，4

因此我们把一个问题转化为另外一个问题了。

此时我们可以手动写下两种前序遍历：

1. 如上所示：

　　经过简单改变变成镜像的前序遍历，先走右边，再走左边

　　if(root!=null){

　　　　//进入之前记录进入的数组

　　　　stack.add(root);

　　　　root = root.right;

　　}else{

　　　　// 弹出上一个节点的值

　　　　root = stack.pop();

　　　　// 此时走左边；

　　　　root= root.left

　　}

　　将记录入栈的结果反转就可以了，你用另外一个栈记录也行。

2. 方法：

　　　这是先序遍历非递归的另外一种写法：

　　　这种虽然有弹栈的操作，走的路径不一样罢了，是先将右边的入栈，然后再入左边的。  

 　　此时稍加改造

说明前序遍历很重要，学会了前序遍历就相当于学会了后序遍历和中序遍历。