零、导言

一、例子引入

1、题目描述

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

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

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

2、题目分析

  （1）题目中要求的“从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印”，也就是层序遍历的内容。有别于树的遍历中的 前序、中序以及后续遍历中使用的深度优先搜索，这里实现树的层序遍历利用的是 广度优先搜索 ；
  （2）实现树的层序遍历具体的做法是维护一个队列 q 和一个答案容器 ret ：队列用来存放树的节点，答案容器用来存放最终的输出答案。完成好准备工作之后，进行如下操作：

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

  （3）可能会有读者有这样的疑问，对于二叉树我们知道有左子树和右子树，如果是 N叉树 的情况，如何知道该树有几个子节点呢？这个就要看树的结构了，一般在答题区域都会有已经实现了的结构体或类了。可以参照 LeetCode 429. N 叉树的层序遍历 中答题区域的 N叉树 数据结构的实现。

3、算法实现与解释

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        if(root == NULL){
            return {};
        }
        vector<int> ret;
        queue<TreeNode*> 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;
    }
};

二、概念定义

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

1、定义

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

在下图所示的广度优先搜索的示例图中：坐标（1，2）处有一个“小人”，可以向左、右、上、下四个方向移动，每次移动仅可以沿着一个方向移动一格。每一个方格内都一个数字，表示“小人”行走到该方格内所需的行动步数。数值相同的方格表示这些方格处于同一层中。通过某一方格向外扩散实现“小人”行走到任意方格的目的。该图是一个典型的广度优先搜索的例子。

广度优先搜索示意图

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

2、深入理解

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

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

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

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

3、相关知识

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

三、相关习题