题目描述
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
假设有这样一棵二叉树，那么它经过层序遍历的结果就应该是：
[[3],[9,20],[15,7]]
解法
我们可以用广度优先搜索解决这个问题。
- 按层打印： 题目要求的二叉树的 从上至下 打印（即按层打印），又称为二叉树的 广度优先搜索，通常借助 队列 的先入先出特性来实现。
- 每层打印到一行： 将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。
初始化： 打印结果列表 res = [] ，包含根节点的队列 queue = [root] 。
循环： 当队列 queue 为空时跳出。
新建一个临时列表 tmp ，用于存储当前层打印结果。
当前层打印循环： 循环次数为当前层节点数（即队列 queue 长度）。
出队： 队首元素出队，记为 node。
打印： 将 node.val 添加至 tmp 尾部。
添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue
将当前层结果 tmp 添加入 res 。
返回： 返回打印结果列表 res 即可。
需要注意的是：进行特例处理，当根节点为空，则返回空列表
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;//设置辅助队列
vector<vector<int>> res;//用来存储最终结果
if (root != nullptr) q.push(root);
while (!q.empty()) {
vector<int> tmp;//每一层遍历以前都初始化tmp
//这里需注意由于在for循环的执行过程中q.size()的值会进行更改，因此q.size()只能作为i的起点而不是终点
for(int i = q.size(); i > 0; --i) {
root = q.front();
q.pop();
tmp.push_back(root->val);//在出队列的时刻进行打印，出队列的同时左右结点都入队列
if (root->left != nullptr) q.push(root->left);
if (root->right != nullptr) q.push(root->right);
}
res.push_back(tmp);
}
return res;
}
};
