深度优先与广度优先
深度优先是对广度优先而言的，可以想象去遍历你的电脑文件目录
有两种遍历方案：
- 刨根问底，把第一个文件夹翻到底，然后再返回上一层，翻下个文件夹
- 把一级目录的文件夹先遍历一遍，然后再遍历二级目录……
第一种就是深度优先，第二种就是广度优先
如果我想遍历二叉树：
// 1
// | \
// 9 20
// | \
// 7 15
tree := TreeNode{
Val: 1,
Left: &TreeNode{
Val: 9,
Left: nil,
Right: nil,
},
Right: &TreeNode{
Val: 20,
Left: &TreeNode{
Val: 15,
Left: nil,
Right: nil,
},
Right: &TreeNode{
Val: 7,
Left: nil,
Right: nil,
},
},
}
递归写法
func DFSRecursion(t *TreeNode) {
if t != nil {
fmt.Println(t.Val)
}
if t.Left != nil{
DFS(t.Left) //遍历左分支 是 遍历整个树的 子问题
}
if t.Right != nil{
DFS(t.Right) //遍历右分支 是 遍历整个树的 另一个同级的 子问题
}
}
由于深度优先是很符合 递归思想 的算法（遍历子目录就是遍历根目录的子问题），所以使用递归实现时也会更加方便
再深入一些：因为使用了现有的栈（函数的调用是存在栈中，而 先进后出，后进先出 的逻辑正好符合DFS的要求），而不必自己去维护，所以相比非递归写法要容易
非递归写法
手动维护栈
递归写法既简洁又容易理解，那么为什么还要使用非递归写法呢？
正所谓 成也栈，败也栈：正是因为使用了函数调用次序使用默认栈才导致程序简介又好理解，但在实际使用中，如果树的结构比较复杂（层级比较深）就会出现爆栈的情况（栈的空间不大）所以首要目标就是手动维护一个 栈（此处的栈指的是符合“先进后出、后进先出”逻辑的数据结构，它存在于堆中）
于是有了下面的代码：
func DFS(t *TreeNode) {
stack := make([]*TreeNode, 0) //用切片来模拟一个栈
// ....
}
嵌套循环
在脑海里想象程序的运行过程：为实现二叉树的深度遍历，那么就是向左走到底，走不通的时候回退一格然后向右走，所以就涉及到 —— 走到底、回退
在整个过程中显然回退不会只发生一次，所以 走到底 需要一个循环，回退 也需要一个循环，也就是嵌套循环（因为走到底和回退的条件有一定逻辑关系）
那么就有了下面的代码：
func DFS(t *TreeNode) {
stack := make([]*TreeNode, 0)
for {
for t != nil {
fmt.Println(t.Val)
stack = append(stack, t) //入栈，保存路径
t = t.Left
}
//...
}
}
节点回退
接下来就要考虑回退的事情了，显然根据上面的代码，t.Left 终归会有为 nil 的时候，那么在 内层for循环 后面的代码就是回退的内容了
func DFS(t *TreeNode) {
stack := make([]*TreeNode, 0)
for {
for t != nil {
fmt.Println(t.Val)
stack = append(stack, t)
t = t.Left
}
t = stack[len(stack)-1] //回退至上一级的节点
}
}
向右走
刚刚我们可都是向左走的，右边的节点还没有碰过，所以此时就应该向右走了
func DFS(t *TreeNode) {
stack := make([]*TreeNode, 0)
for {
for t != nil {
fmt.Println(t.Val)
stack = append(stack, t)
t = t.Left
}
t = stack[len(stack)-1] //回退至上一级的节点
if t.Right != nil { //如果上一级右边不为空
t = t.Right //那么就将右边的节点作为根节点root
continue //为什么此处 continue？ 遍历的规则是向左走，而向左走的内容在上面的 for 循环中，此处只是起到更改根节点root的目的
}
//...
}
}
避免走回头路（左）
左边也走完了，右边也走完了，这个节点的子节点就走完了，需要将这个节点出栈
此时的t已经走完了，为了避免又向左走，需要将t置空，根据栈来找到其父节点重复后续步骤
func DFS(t *TreeNode) {
stack := make([]*TreeNode, 0)
for {
for t != nil {
fmt.Println(t.Val)
stack = append(stack, t)
t = t.Left
}
t = stack[len(stack)-1]
if t.Right != nil {
t = t.Right
continue
}
stack = stack[:len(stack)-1] //出栈，此时节点t已经遍历完了
t = nil //将t置空，避免走回头路，直到下一轮循环中 stack 指派新的t
}
}
避免走回头路（右）
刚刚通过重新分配t避免了向左走回头路，可是向右走是在重新得到t后执行的，所以此时程序还是会向右走回头路的
需要一个新的变量 lastVisit 来记录上一次走完的根节点，避免多次回头
func DFS(t *TreeNode) {
stack := make([]*TreeNode, 0)
//var lastVisit *TreeNode 这种方式也可以
lastVisit := t
for {
for t != nil {
fmt.Println(t.Val)
stack = append(stack, t)
t = t.Left
}
t = stack[len(stack)-1]
if t.Right != nil && t.Right != lastVisit { //右边不为空且上次没走过才能继续往下
t = t.Right
continue
}
stack = stack[:len(stack)-1] //出栈，此时节点t已经遍历完了
lastVisit = t //此时的t已经走完了，赋值给 lastVisit
t = nil //将t置空，避免走回头路，直到下一轮循环中 stack 指派新的t
}
}
结束条件
如果栈空了，也就说明我们完成了所有的遍历，所以需要为程序添加结束条件
func DFS(t *TreeNode) {
stack := make([]*TreeNode, 0)
for {
for t != nil {
fmt.Println(t.Val)
stack = append(stack, t)
t = t.Left
}
t = stack[len(stack)-1]
if t.Right != nil {
t = t.Right
continue
}
stack = stack[:len(stack)-1]
t = nil
if len(stack) == 0 {
break
}
}
}
乍一看，上面的代码好像没有问题，但是如果传入的参数 t==nil 呢？ 会在 t = stack[len(stack)-1]处下标越界
为了修复这个问题，可以将结束判断提前（也可以在进入循环前做非空判断）：
func DFS(t *TreeNode) {
stack := make([]*TreeNode, 0) //手动维护的栈
lastVisit := t //用于表示上次访问节点
for {
//一直向下
for t != nil {
fmt.Println(t.Val)
stack = append(stack, t)
t = t.Left
}
if len(stack) == 0 { //如果栈为空说明遍历完毕
return
}
t = stack[len(stack)-1] //走到头了，回溯
if t.Right != nil && t.Right != lastVisit { //上次遍历的节点（不走回头路）
t = t.Right //左节点遍历完成，开始遍历右边
continue
}
stack = stack[:len(stack)-1] //左右均遍历完，出栈
lastVisit = t
t = nil //此处的t其实是作为标记位，用于跳过上面的“一直向下”而直接回溯
}
}
结语
二叉树的深度遍历在数据结构中是比较基础的内容，通过递归方式遍历是比较好理解的，非递归方式我也想了好久，但仍然百思不得其解（还是太菜了），最后在网上找到了答案，经过自己的分析便有了这样一篇文章，也是给以后的自己提供一个快速复习的途径。
Q.E.D.
