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的左孩子入队,右孩子
也是如此。最后,经过若干次循环,当队列中的元素为空时,我们的遍历也就完成了
最后,这道题完整的代码如下:
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
//定义二维数组,作为返回结果
vector<vector<int>> result;
//根节点为空,就直接返回空数组
if (root == NULL) return result;
//定义模拟队列
queue<TreeNode*> que;
//根节点入队
que.push(root);
while (!que.empty()) {
//记录每一层的操作次数
int size = que.size();
//使用current数组来存储每一层遍历的结果
vector<int> current;
//每一层循环size次就可以了
while(size--) {
//取队头元素
TreeNode* node = que.front();
//队头元素出队
que.pop();
//将每一层遍历的元素放入current数组中
current.push_back(node->val);
//看左孩子是否为空,不为空就将左孩子入队
if (node->left != nullptr) que.push(node->left);
if (node->right != nullptr) que.push(node->right);
}
//将current数组放入二维数组当中
result.push_back(current);
}
//最后,返回这个二维数组就可以了!
return result;
}
};