为什么可以用迭代法（非递归的方式）来实现二叉树的前后中序遍历呢？
在队列与栈专题我们就感受到了，匹配问题都是栈的强项，而递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，这就是递归为什么可以返回上一层位置的原因。
此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。
前序遍历（迭代法）
我们先看一下前序遍历。
前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
不难写出如下Go代码: （注意代码中空节点不入栈）
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func preorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}
res := make([]int,0)
// 二叉树的遍历（迭代法）依赖栈来辅助完成
stack := make([]*TreeNode,0)
stack = append(stack,root)
// 初始时根节点已经入栈，后续栈不为空就可以一直遍历
for len(stack) != 0 {
// 栈弹出一个元素加入结果中
curNode := stack[len(stack) - 1]
stack = stack[0:len(stack) - 1]
res = append(res,curNode.Val)
// 先让右节点入栈，后让左节点入栈，这样出栈才会符合根左右
if curNode.Right != nil {
stack = append(stack,curNode.Right)
}
if curNode.Left != nil {
stack = append(stack,curNode.Left)
}
}
return res
}
此时会发现貌似使用迭代法写出前序遍历并不难，确实不难。
此时是不是想改一点前序遍历代码顺序就把中序遍历搞出来了？
其实还真不行！
但接下来，再用迭代法写中序遍历的时候，会发现套路又不一样了，目前的前序遍历的逻辑无法直接应用到中序遍历上。
中序遍历（迭代法）
为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：
- 处理：将元素放进
res数组中 - 访问：遍历节点
分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是再把节点的数值放进res数组中），这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，当前指针向左边走到头的时候，说明左边遍历到底了，可以从栈弹出一个元素，即【左中右】，左边到底，栈中弹出【中】访问，而后遍历【右】，但是【右】又是一颗子树，继续往左走到头才行。
中序遍历，可以写出如下Go代码：
注意体会下面注释中的【遍历】和【访问】的区别
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}
res := make([]int,0)
stack := make([]*TreeNode,0)
cur := root
// 注意体会下面注释中的【遍历】和【访问】的区别
for cur != nil || len(stack) != 0 {
// 当前节点不为nil，说明左边没有走到头，继续往左遍历
if cur != nil {
stack = append(stack,cur)
cur = cur.Left
} else { // 当前节点为空还能来到这里，说明栈非空，栈顶就是当前要访问的元素
cur = stack[len(stack) - 1]
stack = stack[0:len(stack) - 1]
// 当前访问的元素放入结果
res = append(res,cur.Val)
// 当前节点左边遍历完，当前节点也访问过了，即左中以完成，接下来访问当前节点的右子树
cur = cur.Right
}
}
return res
}
后序遍历（迭代法）
再来看后序遍历，先序遍历是中左右，后序遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转res数组，输出的结果顺序就是左右中了，如下图：
所以后序遍历只需要前序遍历的代码稍作修改就可以了，代码如下：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func postorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}
res := make([]int,0)
stack := make([]*TreeNode,0)
stack = append(stack,root)
for len(stack) != 0 {
cur := stack[len(stack) - 1]
stack = stack[0:len(stack) - 1]
res = append(res,cur.Val)
if cur.Left != nil {
stack = append(stack,cur.Left)
}
if cur.Right != nil {
stack = append(stack,cur.Right)
}
}
// 反转遍历的结果
reverse(res)
return res
}
func reverse(arr []int) {
i,j := 0,len(arr) - 1
for i < j {
arr[i],arr[j] = arr[j],arr[i]
i++
j--
}
return
}
总结
此时我们用迭代法写出了二叉树的前后中序遍历，大家可以看出前序和中序是完全两种代码风格，并不像递归写法那样代码稍做调整，就可以实现前后中序。
这是因为前序遍历中访问节点（遍历节点）和处理节点（将元素放进res数组中）可以同步处理，但是中序就无法做到同步！
上面这句话，可能一些同学不太理解，建议自己亲手用迭代法，先写出来前序，再试试能不能写出中序，就能理解了。