RT，二叉树的层序遍历
今天上午刷LeetCode心态崩了，啥题都写不出来，索性来写博客，记录一下做过的题。
题目链接
LeetCode102.二叉树的层序遍历
题目描述
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）
示例：二叉树：[3,9,20,null,null,15,7],
返回其层次遍历结果：[[3], [9,20], [15,7]]
题目解析
在这道题之前我曾经做过二叉树的前中后序遍历等问题，于是一上来想到的就是各种递归的方法，但是百思不得其解。查看答案才发现自己一开始的思路就错了，原来层序遍历与前中后序遍历使用了完全不一样的方法。
这道题中我们运用了 广度优先遍历（BFS） 的方法来解决问题，每次遍历二叉树中一层的元素，然后再接着遍历下一层。
要解决这个问题我们需要用到队列这一数据结构，由于队列具有先入先出的性质，我们每次将遍历到的一层节点压入队列，然后对这些节点进行处理，将这一层节点的子节点压入队列，然后让这一层的节点出队列，再接着处理下一层的节点。
另外一个让我思考的点是，如何在输出的数组中，确定同一层的节点个数。这一问题比较好解决，因为在将一层的节点全部压入队列并处理之前，已经将上一层的节点全部弹出，所以可以在处理每层节点之前先计算这层节点的数量，然后用这个数量值作为限制处理该层的节点就可以了。
代码
使用了两种方法来写代码，一种似乎是参考答案写的，每一层直接进行处理，另一种是我第二次复习时候写的，在处理每一层时新建了一个vector存储每一层的节点，然后再处理结束后将vector加入到答案vector中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>>result;
if(!root)return result;
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
result.push_back(vector<int>());
int size=q.size();
for(int i=0; i<size; i++){
TreeNode* node=q.front();
result.back().push_back(node->val);
if(node->left)q.push(node->left);
if(node->right)q.push(node->right);
q.pop();
}
}
return result;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>>result;
if(!root)return result;
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
vector<int>level;
int size=q.size();
for(int i=0; i<size; i++){
level.push_back(q.front()->val);
if(q.front()->left)q.push(q.front()->left);
if(q.front()->right)q.push(q.front()->right);
q.pop();
}
result.push_back(level);
}
return result;
}
};
|
总结
二叉树的层序遍历作为广度优先遍历的基础，让我理解了bfs这一算法的基本框架，后面还需要再好好学习一下这一方面，毕竟都忘得差不多了。
