前言
接下来我要开始攻克二叉树这一个大难题了，我打算把二叉树分成四个部分进行总结：
- 二叉树的深度优先遍历
- 二叉树的广度优先遍历（也叫层序遍历）
- 二叉树的基本属性求解
- 二叉树其他相关问题（删改、求公共祖先、二叉搜索树等等）
那我也不废话了，直接开始。
1. 二叉树的前序遍历
接下来，我们就将二叉树的前中后序的递归遍历都做一遍，然后再分别将这四种遍历的迭代实现方法也做一遍，基础不牢，地动山摇，我们慢慢来，一步一个脚印学好二叉树！
题目链接：144. 二叉树的前序遍历
题目描述
所谓的前中后序遍历，在前中后的是什么？其实就是根节点，所以我一般习惯用一个口诀来记住前中后序的遍历顺序：
- 前序就是：根左右
- 中序就是：左根右
- 后序就是：左右根
这其实就是按照根在遍历中的顺序划分的遍历方式。来看代码：
代码
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func preorderTraversal(root *TreeNode) (res []int) { var preorder func(node *TreeNode) preorder = func(node *TreeNode) { if node == nil { return } res = append(res, node.Val) // 根 preorder(node.Left) // 左 preorder(node.Right) // 右 } preorder(root) // 调用前序遍历 return res }
我们来看这个代码，其实这就是一个简单的递归遍历的函数，所谓的 “根左右” 其实就是先把 “根” 位置的值给塞进 res 数组而已。
2. 二叉树的中序遍历
那就继续中序遍历
题目链接：94. 二叉树的中序遍历
题目描述
其实刚刚已经介绍过前中后序是怎么样的了，所以我们直接看代码：
代码
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func inorderTraversal(root *TreeNode) (res []int) { var inorder func(node *TreeNode) inorder = func(node *TreeNode) { if node == nil { return } inorder(node.Left) res = append(res, node.Val) inorder(node.Right) } inorder(root) return res }
这里我注释也懒得打了，可以发现他其实比起前序遍历就只是改了一个地方的代码，就是把 根 的位置和向左递归的位置换了一下，这就是中序遍历的遍历方法。
3. 二叉树的后序遍历
一做肯定是得做全套滴
题目链接：145. 二叉树的后序遍历
题目描述
其实现在题目描述也没有什么意义了，知道是后序遍历，我们直接写代码就完了：
代码
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func postorderTraversal(root *TreeNode) (res []int) { var postorder func(node *TreeNode) postorder = func(node *TreeNode) { if node == nil { return } postorder(node.Left) postorder(node.Right) res = append(res, node.Val) } postorder(root) return res }
没有意外，也是朴实无华的改个代码的位置。
现在开胃小菜算是做完了，像前中后这样的遍历其实并没有什么难度，所以我们还需要挑战一下前中后序的非递归遍历，不然不能算是真正学会了这三种遍历的方式。既是锻炼我们的代码能力，也是让我们熟悉二叉树的基本遍历方式，打牢基础，后面才不会越看越懵逼。
4. 前序遍历的非递归实现
这里我就不把题目描述给放出来了，这里我们用的就是第一题
代码与思路
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func preorderTraversal(root *TreeNode) (ans []int) { if root == nil { return } st := list.New() st.PushBack(root) for st.Len() > 0 { node := st.Remove(st.Back()).(*TreeNode) ans = append(ans, node.Val) if node.Right != nil { st.PushBack(node.Right) } if node.Left != nil { st.PushBack(node.Left) } } return ans }
我来讲讲使用迭代法求解的一个流程，采取的是用一个栈来模拟递归的方法（这里我采用的是 go 语言的 list 来模拟栈操作），模拟前序遍历 “根左右” 的遍历方式
- 首先将根（或者说当前走到的节点）的值存入数组
- 然后分别将右节点和左节点入栈，因为出栈的顺序是相反的，所以我们入栈的时候就要这样先入右节点再入左节点，这样出栈遍历的时候就能达成 “根左右” 的遍历方式了
其实核心的步骤就是这两步，那我们继续实现中序的非递归遍历
5. 中序遍历的非递归实现
代码与思路
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func inorderTraversal(root *TreeNode) (ans []int) { st := list.New() cur := root for cur != nil || st.Len() > 0 { if cur != nil { st.PushBack(cur) cur = cur.Left } else { cur = st.Remove(st.Back()).(*TreeNode) ans = append(ans, cur.Val) cur = cur.Right } } return ans }
前序遍历的时候，我们就是不断计算根位置的值，然后只管用栈按顺序遍历二叉树就行了，但是到了中序遍历，我们需要取的是左节点的值，所以我们就需要在左节点遍历的时候边遍历边取值，我们来根据代码梳理一下他的流程
- 将当前节点入栈，然后一直往左遍历直到走到 nil
- 走到 nil 之后，上一个节点，也就是栈顶的元素就是最左节点，输出到 ans
- 然后往右遍历一步，持续这个三步循环
这三步模拟的就是 “左根右” 的遍历方式，刚好也是三步，找到最左，取根，找右，循环往复，就能完成中序遍历了。迭代算法确实不太好想，但是上手模拟一遍还是比较好理解的。
6. 后序遍历的非递归实现
代码与思路
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func postorderTraversal(root *TreeNode) (ans []int) { if root == nil { return } st := list.New() st.PushBack(root) for st.Len() > 0 { node := st.Remove(st.Back()).(*TreeNode) ans = append(ans, node.Val) if node.Left != nil { st.PushBack(node.Left) } if node.Right != nil { st.PushBack(node.Right) } } reverse(ans) return ans } func reverse(a []int) { // 反转数组 l, r := 0, len(a)-1 for l < r { a[l], a[r] = a[r], a[l] l, r = l+1, r-1 } }
后序遍历有一个非常巧妙的解法：因为前序遍历是 “根左右”，后续遍历是 “左右根”，如果我们根据 “根右左” 的顺序来进行遍历，然后再将结果进行反转就能将 “根右左” -> “左右根”，这样就完成了后续遍历，也就是我们只需要修改一下前序遍历的代码即可
就那上述代码来说，我将遍历左右的顺序进行了调换，然后实现了一个 reverse 反转数组（go 语言没有 C++ 那样提供 STL，难受）按照刚刚分析出来的思路实现后序遍历。
总结
基础不牢，地动山摇，把二叉树的前中后序学会，我们下一节挑战二叉树的广度优先遍历，又或者说，二叉树的层序遍历。
