基础扫盲:二叉树系列 第二讲(层次遍历与BFS)
共 1514字，需浏览 4分钟
·
2020-02-04 23:27
来源：浩仔讲算法
作者：浩仔讲算法
在上一节中，我们通过例题学习了二叉树的DFS（深度优先搜索），其实就是沿着一个方向一直向下遍历。那我们可不可以按照高度一层一层的访问树中的数据呢？当然可以，就是本节中我们要讲的BFS（宽度优先搜索），同时也被称为广度优先搜索。
我们仍然通过例题进行讲解：
01第102题：二叉树的层次遍历第102题：给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：[[3],[9,20],[15,7]]
本系列内容均为必须掌握！
BFS，广度/宽度优先。其实就是从上到下，先把每一层遍历完之后再遍历一下一层。假如我们的树如下：
按照BFS，访问顺序如下：
a->b->c->d->e->f->g
了解了BFS，我们开始对本题进行分析。
03递归求解
同样，我们先考虑本题的递归解法。想到递归，我们一般先想到DFS。我们可以对该二叉树进行先序遍历（根左右的顺序），同时，记录节点所在的层次level，并且对每一层都定义一个数组，然后将访问到的节点值放入对应层的数组中。
假设给定二叉树为[3,9,20,null,null,15,7]，图解如下：
根据分析，代码如下：
1func levelOrder(root *TreeNode) [][]int {
2 return dfs(root, 0, [][]int{})
3}
4
5func dfs(root *TreeNode, level int, res [][]int) [][]int {
6 if root == nil {
7 return res
8 }
9 if len(res) == level {
10 res = append(res, []int{root.Val})
11 } else {
12 res[level] = append(res[level], root.Val)
13 }
14 res = dfs(root.Left, level+1, res)
15 res = dfs(root.Right, level+1, res)
16 return res
17}
上面的解法，其实相当于是用DFS的方法实现了二叉树的BFS。那我们能不能直接使用BFS的方式进行解题呢？当然，我们可以使用Queue的数据结构。我们将root节点初始化进队列，通过消耗尾部，插入头部的方式来完成BFS。
具体步骤如下图：
根据分析，完成代码：
1//go
2func levelOrder(root *TreeNode) [][]int {
3 var result [][]int
4 if root == nil {
5 return result
6 }
7 // 定义一个双向队列
8 queue := list.New()
9 // 插入根结点完成初始化
10 queue.PushFront(root)
11 // 进行广度搜索
12 for queue.Len() > 0 {
13 var current []int
14 listLength := queue.Len()
15 for i := 0; i < listLength; i++ {
16 // 消耗尾部
17 // queue.Remove(queue.Back()).(*TreeNode)：移除最后一个元素并将其转化为TreeNode类型
18 node := queue.Remove(queue.Back()).(*TreeNode)
19 current = append(current, node.Val)
20 if node.Left != nil {
21 //插入头部
22 queue.PushFront(node.Left)
23 }
24 if node.Right != nil {
25 queue.PushFront(node.Right)
26 }
27 }
28 result = append(result, current)
29 }
30 return result
31}注：本系列所有教程中都不会用到复杂的语言特性，大家不需要担心没有学过相关语法。算法思想最重要，使用各语言纯属本人爱好。同时，本系列所有代码均在leetcode上进行过测试运行，保证其严谨性！
推荐阅读