前置知识：二叉树、先序、中序、后序、栈
建议：不要跳过
递归与迭代
理论上来说，一切递归都可以被改写成迭代（循环）实现，因为递归的本质就是利用系统调用栈进行迭代，我们可以自己模拟出系统调用栈的执行过程，即可改写
递归依赖系统调用栈，系统调用栈空间较小（较堆），可能导致栈溢出的错误；而且每一层递归都要创建出一个“栈帧”，栈帧会多出一些指针来维持上下文关系，比较重（较自己实现的栈）
所以，一般情况下，迭代实现比递归实现更好
那么，是否要将所有的递归都改写成迭代实现呢？并不是！
时间、空间并不是检验算法优劣的唯一度量，还要考虑代码的编写复杂度、代码可读性等问题
递归改写成迭代可能会导致代码可读性很差，或者导致代码很复杂（甚至根本无法写出）；改写成迭代后时空占用甚至不如递归实现的情况也很常见
如：这道题 迭代实现要使用 3 个队列才能模拟出递归实现的逻辑，而且其代码复杂度和可读性较递归实现要差很多
迭代实现二叉树前序、中序、后序遍历
实现过好多遍了，就不再写了
前序只需要一个栈就可以模拟；中序需要一个栈和一个指向二叉树节点的 cur 指针；后序需要将结果逆序，需要多加一个用于逆序的栈，而且后序并不是完全模拟递归的逻辑，而是将结果逆序而进行取巧
后序遍历：逆序取巧
// 后序取巧：“左右根” -> “根右左”后逆序
func postorderTraversal(root *TreeNode) []int {
ans := []int{}
stack := []*TreeNode{}
if root != nil {
stack = append(stack, root)
}
for len(stack) > 0 {
cur := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
ans = append(ans, cur.Val)
if cur.Left != nil {
stack = append(stack, cur.Left)
}
if cur.Right != nil {
stack = append(stack, cur.Right)
}
}
reverse(ans) // 逆序
return ans
}
func reverse(arr []int) {
left, right := 0, len(arr) - 1
for left < right {
arr[left], arr[right] = arr[right], arr[left]
left++
right--
}
}
// 因为这里是收集顺序到一个数组，所以就不需要多加一个用于逆序的栈了，而是对结果数组进行逆序
// 如果是按顺序打印的话，就需要多加一个用于逆序的栈后序遍历：last 指针
用两个栈实现二叉树后序遍历（上面的“逆序取巧”方法），好写但是不推荐，因为需要收集所有节点，最后逆序弹出，额外空间复杂度为 O(n)
还有一种思路不需要逆序取巧，而是要加一个指向上一次处理节点的 last 指针
func postorderTraversal(root *TreeNode) []int {
ans := []int{}
// 如果始终没有处理过节点，last 就一直是头节点
// 一旦处理了节点，last 就变成处理节点
// 即：last 指向上一次处理的节点
last := root
stack := []*TreeNode{}
if root != nil {
stack = append(stack, root)
}
for len(stack) > 0 {
lastIdx := len(stack) - 1
cur := stack[lastIdx]
if cur.Left != nil && last != cur.Left && last != cur.Right {
// 有左树且左树没处理过
stack = append(stack, cur.Left)
} else if cur.Right != nil && last != cur.Right {
// 有右树且右树没处理过
stack = append(stack, cur.Right)
} else {
// 左右树都没有 或 都处理过了
ans = append(ans, cur.Val)
last = cur
stack = stack[:lastIdx]
}
}
return ans
}迭代的统一写法
前中后序迭代实现写法和逻辑还不相同，为什么这么坑爹？归根结底是因为节点入栈的顺序和需要对节点进行操作的顺序不能相对应，即：访问节点（遍历节点）和处理节点（将元素放进结果集或打印）不⼀致的情况
只需要解决这种不一致的情况，前中后序迭代就可以用统一的逻辑进行实现了
如何统一不一致？做标记：将访问的节点放⼊栈中，把要处理的节点也放⼊栈中但是要做标记；如何标记？就是要处理的节点放⼊栈之后，紧接着放⼊⼀个空指针作为标记
func order(root *TreeNode) []int {
ans := []int{}
stack := []*TreeNode{}
if root != nil {
stack = append(stack, root)
}
for len(stack) > 0 {
lastIdx := len(stack) - 1
cur := stack[lastIdx]
if cur == nil { // 遇见了标记，说明下一个元素就是我们要处理的结果
ans = append(ans, stack[lastIdx - 1].Val) // 处理
stack = stack[:lastIdx - 1]
} else {
stack = stack[:lastIdx]
// 位置一：后序
// stack = append(stack, cur, nil) // 做标记
if cur.Right != nil {
stack = append(stack, cur.Right)
}
// 位置二：中序
if cur.Left != nil {
stack = append(stack, cur.Left)
}
// 位置三：前序
}
}
return ans
}这里的位置一、二、三和 递归序 中的第三、二、一次访问是是一样的逻辑（相反是栈后进先出的特点导致的）
迭代遍历二叉树复杂度分析
- 时间复杂度
O(n)- 递归和迭代都是每个节点遇到有限几次
- 额外空间复杂度
O(h)，h是二叉树的高度- 递归和迭代都需要二叉树高度
h的空间来保存路径，方便回到上级去 - 迭代：自己建的栈空间；递归：系统调用栈空间
- 递归和迭代都需要二叉树高度
Morris 遍历
存在时间复杂度 O(n)，额外空间复杂度 O(1) 的遍历方式：Morris 遍历
Morris 遍历的基本思路是利用叶子节点左右子树指针的空间联系出处理顺序，最后在将其指向还原为 nil
Morris 遍历比较难，也比较冷门，会在【扩展】课程里讲述