上次讲过了 二叉树的深度遍历，这次来看看广度遍历

其实以前在学校里做数据结构的习题时我就喜欢广度遍历（毕竟已经一层一层的分好了，可以直接写答案），更符合人脑的直觉

还是和上次一样的数据结构

//	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 levelOrderRecursion(t *TreeNode) [][]int {
	return dfs(t, [][]int{}, 0) //根节点、存储每一级元素的二维数组和当前层数
}

接下来就是常规的dfs了
递归思路：n层树结构(n>1)遍历可以拆分成 一层（当前层） 和 下面的子树 遍历，这两个子问题

func dfs(root *TreeNode, res [][]int, level int) [][]int {
	if root == nil {
		return res //如果root为空说明走到头，要回头了
	}
	if len(res) == level { //如果当前元素是 level 层 的第一个元素
		res = append(res,[]int{}) //为level层添加一个空行
	}
	res[level] = append(res[level],root) //将当前元素装入对应层的位置
	res = dfs(t.Left,res,level+1) //对当前节点的左子树执行相同操作
	res = dfs(t.Right,res,level+1) //对当前节点的左子树执行相同操作
	return res
}

非递归解法

和之前一样，递归方案由于函数调用开销、栈空间小等原因，在真正开发时使用得不多，更多应该使用非递归解法

双层循环

遍历n层二叉树，每一层又有多个节点，所以要使用双层for循环

func levelOrder(t *TreeNode) [][]int {
	for {
		//层级遍历
		for {
			//层内遍历
		}
	}
	//...
}

相邻两行的关系

在遍历上一层的同时就可以对下一层的内容进行扫描，作为下次循环的当前行，所以需要一个切片来保存当前行、一个切片来保存下一行

func levelOrder(t *TreeNode) [][]int {
	res := make([][]int,0) //用于保存结果
	currentLevel := []*TreeNode{t} //当前行
	for level := 0;;level++ {
		nextLevel := []*TreeNode{}//保存下一行
		res = append(res,[]int{})//用于保存当前行的结果
		for _,v := range currentLevel {
			if v != nil {
				res[level] = append(res[level],v)
				//扫描下一行的内容并存入 nextLevel 中
				if v.Left != nil {
					nextLevel = append(nextLevel,v.Left)
				}
				if v.Right != nil {
					nextLevel = append(nextLevel,v.Right)
				}
			}
		}
		currentLevel = nextLevel //下一行作为下次循环的当前行
	}
	//...
}

层级遍历结束条件

在内层循环中，如果当前层的所有元素均没有子节点，那么 nextLevel 的长度就是0，最后传递给 currentLevel 的长度也是0
所以当 currentLevel 长度为0时，说明遍历完成了

func levelOrder(t *TreeNode) [][]int {
	res := make([][]int,0)
	currentLevel := []*TreeNode{t}
	for level := 0;len(currentLevel)!=0;level++ { // 当 currentLevel 长度为0时，说明遍历完成了
		nextLevel := []*TreeNode{}
		res = append(res,[]int{})
		for _,v := range currentLevel {
			if v != nil {
				res[level] = append(res[level],v)
				if v.Left != nil {
					nextLevel = append(nextLevel,v.Left)
				}
				if v.Right != nil {
					nextLevel = append(nextLevel,v.Right)
				}
			}
		}
		currentLevel = nextLevel 
	}
	return res //输出结果
}

非空判断

由于 res = append(res,[]int{}) 的缘故，当传入 [] 空树时，会返回 [[]] 结果，而这不是我们想要的

func levelOrder(t *TreeNode) [][]int {
	if t == nil { //加入一个非空判断
		return [][]int{}
	}
	res := make([][]int,0)
	currentLevel := []*TreeNode{t}
	for level := 0;len(currentLevel)!=0;level++ {
		nextLevel := []*TreeNode{}
		res = append(res,[]int{})
		for _,v := range currentLevel {
			if v != nil {
				res[level] = append(res[level],v)
				if v.Left != nil {
					nextLevel = append(nextLevel,v.Left)
				}
				if v.Right != nil {
					nextLevel = append(nextLevel,v.Right)
				}
			}
		}
		currentLevel = nextLevel 
	}
	return res
}

结语

和 深度遍历 相反，这次是自己实现的非递归方式，在非递归解法上，个人感觉广度遍历貌似比深度遍历要简单一些
递归由于其本身的劣势（例如函数调用的开销、栈空间小等），所以通常解决问题时不会优先使用递归，但这仍然是一种经典、有效的解题思路
和上次一样，留下一个给自己快速复习的途径，如果还能帮到你理解那就更好了。

Q.E.D.