😯最近一段时间，突然有点儿兴趣，刷刷数据结构。在刷的过程中，发现二叉树的递归遍历比较好，迭代后续遍历没有那么好写，也困扰了我一天。
🚗🚗🚗🚗今天就在炽热的天空下，凉凉的空调房里写一下如何使用栈实现二叉树的迭代后序遍历。
目录
一、二叉树迭代后续遍历需要思考的问题
二叉树的递归遍历，整体上都是一个结构套着出来的，就是打印根节点的位置不一样。就是递归左子树节点，打印根节点，递归右子树节点的组合。
根节点，在中间取值则是中序遍历。
func midRecur(root *TreeNode) []int {
var res []int
if root==nil {
return res
}
left := midRecur(root.Left)
val := root.Val
right := midRecur(root.Right)
res = append(res, left...)
res = append(res, val)
res = append(res, right...)
return res
}
二、🍻二叉树后序迭代遍历实现
后序迭代遍历的实现，其实就是手动模拟后续遍历二叉树的递归实现。但是这里面有一点小坑的就是，后续遍历二叉树是需要先把左右子树遍历完了，再访问根节点的值。这个时候就需要定义一个变量额外记录访问过的变量。
2.1🍺🍺🍺 二叉树定义
二叉树的定义是中规中矩喽~
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}2.2 🍖🍖🍖二叉树后续迭代遍历演化
这一块内容，就是逐步推演如何使用非递归遍历实现二叉树的后续。
2.2.1 一杆子捅到底
通过前面的二叉树后续递归遍历的代码，我们了解到二叉树的后续遍历，就是先访问左子树，再访问右子树。从结果上，我们也可以了解到首先打印的是最左边，最下面的节点。根据栈先进后出的特点，所以我们了解到要先把所有的最左侧的节点灌到栈里面。
func postIteration(root *TreeNode) []int {
l := list2.New()
back:=root
var res []int
for l.Len() != 0 || back != nil {
for back!=nil {
l.PushBack(back)
back=back.Left
}
element := l.Back() //取出栈顶元素
top := element.Value.(*TreeNode) //类型转换
}
return res
}2.3 🍟🍟🍟栈顶出数，路在何方
上面的代码呢，我们已经最左侧的节点，都丢到栈里面了。丢完了以后呢，我们要取出来开始遍历数据了呢。首先呢，通过栈递归呢，我们知道，我们第一次取出的这个数据，是没有左子树的，但是可能有右子树。如果有右子树，那么右子树也需要入栈。如果没有右子树，这个节点的数据就可以取出并移除。
func postIteration(root *TreeNode) []int {
l := list2.New()
back:=root
var res []int
for l.Len() != 0 || back != nil {
for back!=nil {
l.PushBack(back)
back=back.Left
}
element := l.Back() //取出栈顶元素
top := element.Value.(*TreeNode) //类型转换
//右子树不为空，那么右子树也需要入栈
if top.Right!=nil {
back=top.Right
}else {
//右子树为空，取出值
res = append(res, top.Val)
l.Remove(element)
back=nil //取出来值的时候，要把需要入栈的子树置位nil,否则会死循环。
}
}
return res
}执行结果：意外的是，上面这段代码又陷入死循环。
死循环原因：上述代码，增加了一个逻辑判断，就是当栈顶元素E的右子树存在时，开始对右子树进行入栈。但是呀，但是呀，这里有一个问题啦，那就是右子树入栈的时候，并没有把原来栈顶元素E弹出来呀！也就是说，这段代码，又卡死在一个循环里。
2.3 🍟🍟🍟一次就好，整太多没用
闲言少叙，再接上文。这个代码死循环的原因就在于对栈顶元素右子树的判断。举一个简单例子，对一个后序遍历为235的树，当栈中的数据只剩跟5的时候，会判断有没有右子树，有的话，把右子树3入栈。当3出栈，栈中只有根5的时候，这个根5又会判断有没有右子树，有的话，又会把3入栈，循环往复，栈就溢出了。程序就崩溃了。
那这个问题的根源在哪，在于这个根5，他访问不知道右子树被访问过，来来回回，折磨电脑，就是打印不出。那么解决问题的办法就是让根有意义，让根知道谁被访问过~
func postIteration(root *TreeNode) []int {
l := list2.New()
back := root
var res []int
var visited *TreeNode //增加一个标志位，确认节点是否被访问过
for l.Len() != 0 || back != nil {
for back != nil {
l.PushBack(back)
back = back.Left
}
element := l.Back() //取出栈顶元素
top := element.Value.(*TreeNode) //类型转换
//右子树不为空，那么右子树也需要入栈，且top的右子树不能被访问过，
if top.Right != nil && visited != top.Right {
back = top.Right
} else
{
res = append(res, top.Val)
l.Remove(element)
visited =top
//这里就没有需要入栈的元素了，要不然取出来，又扔进去了
back = nil
}
}
return res
}leetCode代码测试成功哦~
三、🍏🍏🍏总结
纸上得来终觉浅，绝知此事要躬行。我会尽量在我的博客里面留下我自己思考的内容💪🏻⛽️~
🧧🧧🧧感谢诸位大佬的阅读，点个关注，收藏一下呗~
