11##题目地址
22https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
33
4+ > 我要打十个！
5+
6+ 看完这篇文章虽然不能打十个，但是可以迅速打五个！而且够快！
7+
8+
9+ #102.二叉树的层序遍历
10+
11+ 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
12+
13+ <img src =' ../pics/102.二叉树的层序遍历.png ' width =600 > </img ></div >
14+
415##思路
516
6- 我们之前讲过了，二叉树的深度优先遍历：[ 一文学通二叉树前中后序递归法与迭代法] ( https://github.com/youngyangyang04/leetcode/blob/master/problems/0144.二叉树的前序遍历.md ) 里面有前中后序遍历的方式，前中后序分辨可以使用递归和迭代的方法来实现，接下来我们再来介绍二叉树的另一种遍历方式，也就是层序遍历。
17+ 我们之前讲过了三篇关于二叉树的深度优先遍历的文章：
18+
19+ * [ 二叉树：前中后序递归法] ( https://mp.weixin.qq.com/s/PwVIfxDlT3kRgMASWAMGhA )
20+ * [ 二叉树：前中后序迭代法] ( https://mp.weixin.qq.com/s/c_zCrGHIVlBjUH_hJtghCg )
21+ * [ 二叉树：前中后序迭代方式统一写法] ( https://mp.weixin.qq.com/s/WKg0Ty1_3SZkztpHubZPRg )
722
8- 相似题目：
9- * [ 0102.二叉树的层序遍历] ( https://github.com/youngyangyang04/leetcode/blob/master/problems/0102.二叉树的层序遍历.md )
10- * [ 0107.二叉树的层次遍历II] ( https://github.com/youngyangyang04/leetcode/blob/master/problems/0107.二叉树的层次遍历II.md )
11- * [ 0199.二叉树的右视图] ( https://github.com/youngyangyang04/leetcode/blob/master/problems/0199.二叉树的右视图.md )
12- * [ 0637.二叉树的层平均值] ( https://github.com/youngyangyang04/leetcode/blob/master/problems/0637.二叉树的层平均值.md )
23+ 接下来我们再来介绍二叉树的另一种遍历方式：层序遍历。
1324
1425层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
1526
16- 需要借用一个辅助数据结构队列来实现 ，** 队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。**
27+ 需要借用一个辅助数据结构即队列来实现 ，** 队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。**
1728
18- 使用队列实现广度优先遍历，动画如下：
29+ ** 而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。 **
1930
31+ 使用队列实现二叉树广度优先遍历，动画如下：
32+
33+ ![ 102二叉树的层序遍历.mp4] ( ad3d58a5-b8ee-42a5-bc89-6ad4d9e3cbf2 )
2034<video src =' ../video/102二叉树的层序遍历.mp4 ' controls =' controls ' width =' 640 ' height =' 320 ' autoplay =' autoplay ' > Your browser does not support the video tag.</video ></div >
2135
2236这样就实现了层序从左到右遍历二叉树。
2337
24- 代码如下：这份代码也可以作为二叉树层序遍历的模板。
38+ 代码如下：** 这份代码也可以作为二叉树层序遍历的模板，以后在打四个就靠它了 ** 。
2539
2640##C++代码
2741
@@ -35,7 +49,8 @@ public:
3549 while (!que.empty()) {
3650 int size = que.size();
3751 vector<int> vec;
38- for (int i = 0; i < size; i++) {// 这里一定要使用固定大小size，不要使用que.size()
52+ // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
53+ for (int i = 0; i < size; i++) {
3954 TreeNode* node = que.front();
4055 que.pop();
4156 vec.push_back(node->val);
@@ -49,4 +64,186 @@ public:
4964};
5065```
5166
67+ ** 此时我们就掌握了二叉树的层序遍历了，那么如下四道leetcode上的题目，只需要修改模板的一两行代码（不能再多了），便可打倒！**
68+
69+ #107.二叉树的层次遍历 II
70+
71+ 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
72+
73+ <img src =' ../pics/107.二叉树的层次遍历II.png ' width =600 > </img ></div >
74+
75+ ##思路
76+
77+ 相对于102.二叉树的层序遍历，就是最后把result数组反转一下就可以了。
78+
79+ ##C++代码
80+
81+ ```
82+ class Solution {
83+ public:
84+ vector<vector<int>> levelOrderBottom(TreeNode* root) {
85+ queue<TreeNode*> que;
86+ if (root != NULL) que.push(root);
87+ vector<vector<int>> result;
88+ while (!que.empty()) {
89+ int size = que.size();
90+ vector<int> vec;
91+ for (int i = 0; i < size; i++) {
92+ TreeNode* node = que.front();
93+ que.pop();
94+ vec.push_back(node->val);
95+ if (node->left) que.push(node->left);
96+ if (node->right) que.push(node->right);
97+ }
98+ result.push_back(vec);
99+ }
100+ reverse(result.begin(), result.end()); // 在这里反转一下数组即可
101+ return result;
102+
103+ }
104+ };
105+ ```
106+
107+
108+ #199.二叉树的右视图
109+
110+ 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
111+
112+ <img src =' ../pics/199.二叉树的右视图.png ' width =600 > </img ></div >
113+
114+ ##思路
115+
116+ 层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。
117+
118+ ##C++代码
119+
120+ ```
121+ class Solution {
122+ public:
123+ vector<int> rightSideView(TreeNode* root) {
124+ queue<TreeNode*> que;
125+ if (root != NULL) que.push(root);
126+ vector<int> result;
127+ while (!que.empty()) {
128+ int size = que.size();
129+ for (int i = 0; i < size; i++) {
130+ TreeNode* node = que.front();
131+ que.pop();
132+ if (i == (size - 1)) result.push_back(node->val); // 将每一层的最后元素放入result数组中
133+ if (node->left) que.push(node->left);
134+ if (node->right) que.push(node->right);
135+ }
136+ }
137+ return result;
138+ }
139+ };
140+ ```
141+
142+ #637.二叉树的层平均值
143+
144+ 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
145+
146+ <img src =' ../pics/637.二叉树的层平均值.png ' width =600 > </img ></div >
147+
148+ ##思路
149+
150+ 本题就是层序遍历的时候把一层求个总和在取一个均值。
151+
152+ ##C++代码
153+
154+ ```
155+ class Solution {
156+ public:
157+ vector<double> averageOfLevels(TreeNode* root) {
158+ queue<TreeNode*> que;
159+ if (root != NULL) que.push(root);
160+ vector<double> result;
161+ while (!que.empty()) {
162+ int size = que.size();
163+ double sum = 0; // 统计每一层的和
164+ for (int i = 0; i < size; i++) {
165+ TreeNode* node = que.front();
166+ que.pop();
167+ sum += node->val;
168+ if (node->left) que.push(node->left);
169+ if (node->right) que.push(node->right);
170+ }
171+ result.push_back(sum / size); // 将每一层均值放进结果集
172+ }
173+ return result;
174+ }
175+ };
176+
177+ ```
178+
179+ #429.N叉树的层序遍历
180+
181+ 给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
182+
183+ 例如，给定一个 3叉树 :
184+
185+
186+ <img src =' ../pics/429. N叉树的层序遍历.png ' width =600 > </img ></div >
187+
188+ 返回其层序遍历:
189+
190+ [
191+ [ 1] ,
192+ [ 3,2,4] ,
193+ [ 5,6]
194+ ]
195+
196+
197+ ##思路
198+
199+ 这道题依旧是模板题，只不过一个节点有多个孩子了
200+
201+ ##C++代码
202+
203+ ```
204+ class Solution {
205+ public:
206+ vector<vector<int>> levelOrder(Node* root) {
207+ queue<Node*> que;
208+ if (root != NULL) que.push(root);
209+ vector<vector<int>> result;
210+ while (!que.empty()) {
211+ int size = que.size();
212+ vector<int> vec;
213+ for (int i = 0; i < size; i++) {
214+ Node* node = que.front();
215+ que.pop();
216+ vec.push_back(node->val);
217+ for (int i = 0; i < node->children.size(); i++) { // 将节点孩子加入队列
218+ if (node->children[i]) que.push(node->children[i]);
219+ }
220+ }
221+ result.push_back(vec);
222+ }
223+ return result;
224+
225+ }
226+ };
227+ ```
228+
229+ #总结
230+
231+ 二叉树的层序遍历，就是图论中的广度优先搜索在二叉树中的应用，需要借助队列来实现（此时是不是又发现队列的应用了）。
232+
233+ 学会二叉树的层序遍历，可以一口气撸完leetcode上五道题目：
234+
235+ * 102.二叉树的层序遍历
236+ * 107.二叉树的层次遍历II
237+ * 199.二叉树的右视图
238+ * 637.二叉树的层平均值
239+ * 589.N叉树的前序遍历
240+
241+ 虽然不能一口气打十个，打五个也还行。
242+
243+ 如果非要打十个，还得找叶师傅！
244+
245+ <img src =' ../pics/我要打十个.gif ' width =600 > </img ></div >
246+
247+
248+
52249> 更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。