广度优先搜索（1）之树的层序遍历

• 零、导言
• 一、例子引入
• • 1、题目描述
  • 2、题目分析
  • 3、算法实现与解释
• 二、概念定义
• • 1、定义
  • 2、深入理解
  • 3、相关知识
• 三、相关习题

剑指 Offer 32 - I. 从上到下打印二叉树

  从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
输入：

返回：
[3,9,20,15,7] texttt{[3,9,20,15,7]} [3,9,20,15,7]

  （1）题目中明确说明了是按照层进行遍历输出的，也就是层序遍历。有别于树的遍历中的 前序、中序以及后续遍历中使用的深度优先搜索，这里是利用 广度优先搜索 实现的层序遍历；
  （2）具体的做法就是维护一个队列 q 和一个答案容器 ret ：队列用来存放树的节点，答案容器用来存放最终的输出答案。

• 首先把根节点存入队列 q ；
• 队列只要不为空就一直循环读取队列中的队首元素：
    当前读取的队首元素存入 ret ，当当前读取的队首元素还有子节点的话依次把左子节点、右子节点存入队列；

  （3）可能会有人说，这是二叉树所以知道是有左子树和右子树，那要是 N叉树 的情况，怎么知道到底有几点子节点呢？这个就要看树的结构了，一般在答题区域都会有已经实现了的结构体或类了。可以参照 LeetCode 429. N 叉树的层序遍历 中答题区域的 N叉树 数据结构的实现。

class Solution {
public:
    vector levelOrder(TreeNode* root) {
        if(root == NULL){
            return {};
        }
        vector ret;
        queue Q;			
        Q.push(root);						// push根节点

        while(!Q.empty()){					// 循环的条件
            TreeNode* now = Q.front();		// 读取队首元素
            ret.push_back(now->val);		// push进答案容器
            Q.pop();

            if(now->left){					// 判断是否有左子节点
                Q.push(now->left);
            }
            if(now->right){					// 判断是否有右子节点
                Q.push(now->right);			
            }
        }
        return ret;
    }
};

例子看完了，相信大家对这个题目以及 广度优先搜索——层序遍历 已经有了初步的认识了。现在我们来详细解读一下广度优先搜索和层序遍历。

维基百科 广度优先搜索算法 （英语：Breadth-First Search，缩写为BFS），又译作 宽度优先搜索 ，或 横向优先搜索 ，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。

层序遍历： 是树众多遍历算法中的一种。有前序遍历、中序遍历、后续遍历和层序遍历等等。
以上提及的遍历方法的定义以及求解方法见下表所示：

通过做一些广搜类和深搜类的算法题目，我们可以发现：

• 对于深搜类的题目会用到 栈 这种数据结构（一般会使用 vector<> 容器来代替）；
• 对于广搜类的题目，我们会使用到 queue<> 队列 这种数据结构，有时候也会使用 priority_queue<> 优先队列 这种数据结构

那为什么会是这样呢？
还是要从定义出发，以树结构为例：

• 深搜要一头扎到底，从树的根节点一直扎到叶子节点，然后再慢慢的回溯，这就会涉及到 后入先出 的问题，具体的在 深度优先搜索 的章节再细讲。
• 广度优先搜索，广搜从树的根节点开始，沿着树的宽度方向开始搜索，依次加入当前层的各个子节点，然后再依次读取各个子节点的子节点。直到队列为空，结束循环。
  以例子中的二叉树为例：
  

通过以上的分析，可以发现熟知 队列 的相关操作是十分必要的。
参照 四、总结（4）回顾队列知识。