LeetCode102.二叉树的层序遍历

LeetCode题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/submissions/548489149/

题目叙述：

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

这道题就是简单的叫我们求层序遍历的代码，二叉树的层序遍历实际上就是一个广度优先遍历（BFS），我们可以用一个队列来模仿这个过程。
步骤1

1.力扣上面的原题要求我们返回一个二维数组，即每个一维数组存储每一层遍历的效果，我们首先界说一个vector的二维数组result，如果传入的根节点为空，我们直接返回这个空的二维数组即可。
步骤2

2.如果根节点不为空的话，我们界说一个队列queue，并将根节点入队。
步骤3

3.接下来我们就是来模仿层序遍历的过程了，我们在队列里操作这颗二叉树的节点时，当队列为空，二叉树是不是就已经遍历完了？可以本技艺动模仿试一试，可以很容易的发现，当队列为空时，我们的二叉树
就遍历完了，因此，我们的外层循环条件为队列不为空
步骤4

4.由于我们的题目要求我们要返回每一层遍历的效果，因此，我们需要一个元素来记录我们当前层次的元素个数，怎么记录呢？————就是当前队列的元素个数，因此，我们可以使用size变量来存储我们当前
层次的元素个数，并用一个数组current来记录当前层次遍历的效果，最后每一次将current放入result即可，接下来就进入循环的过程了，我们遍历每一层的时候操作size次，就可以将当前层次的元素全部
遍历，并且将下一层的元素全部入队。
怎么将队列中的元素放进数组呢？

我们在单层循环内，可以使用node变量，来取出我们队列的头部元素，同时将头部元素出队，并将node->val存入当前数组current中，判定node的左孩子是否为空，若不为空，就将node的左孩子入队，右孩子
也是如此。最后，颠末若干次循环，当队列中的元素为空时，我们的遍历也就完成了
最后，这道题完整的代码如下：

1. class Solution {
2. public:
3.         vector<vector<int>> levelOrder(TreeNode* root) {
4.                 //定义二维数组，作为返回结果
5.                 vector<vector<int>> result;
6.                 //根节点为空，就直接返回空数组
7.                 if (root == NULL) return result;
8.                 //定义模拟队列
9.                 queue<TreeNode*> que;
10.                 //根节点入队
11.                 que.push(root);
12.                 while (!que.empty()) {
13.                         //记录每一层的操作次数
14.                         int size = que.size();
15.                         //使用current数组来存储每一层遍历的结果
16.                         vector<int> current;
17.                         //每一层循环size次就可以了
18.                         while(size--) {
19.                                 //取队头元素
20.                                 TreeNode* node = que.front();
21.                                 //队头元素出队
22.                                 que.pop();
23.                                 //将每一层遍历的元素放入current数组中
24.                                 current.push_back(node->val);
25.                                 //看左孩子是否为空，不为空就将左孩子入队
26.                                 if (node->left != nullptr) que.push(node->left);
27.                                 if (node->right != nullptr) que.push(node->right);
28.                         }
29.                         //将current数组放入二维数组当中
30.                         result.push_back(current);
31.                 }
32.                 //最后，返回这个二维数组就可以了！
33.                 return result;
34.         }
35. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。