给你一个二叉树,请你返回其按层序遍历得到的结点值。(即逐层地,从左到右访问所有结点)。
示例:
输入:二叉树:[3, 9, 20, null, null, 15, 7]
输出:[
[3],
[9, 20],
[15, 7]
]
思路:
该题目考察的就是二叉树的层序遍历,只不过要求我们将遍历结果放入vector容器当中返回而已。
解决该题目需要一个队列q和两个vector容器,队列q用于存储结点的地址,两个vector容器当中,v用于存储二叉树某一层的结点值,vv用于存储整个二叉树的结点值。
操作步骤如下:
- 先将根结点入队列。
- 从队头取levelSize个(初始levelSize为1)结点放入容器v,若取出结点左右孩子不为空,还需将不为空的孩子结点放入队列。
- 将容器v放入容器vv当中,即第该层的结点值。
- 更新levelSize的值为当前队列当中的元素个数,继续进行步骤2和步骤3,直至队列为空。
代码如下:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (root == nullptr) //空树直接返回
{
return vector<vector<int>>();
}
queue<TreeNode*> q;
//1、先将根入队列
q.push(root);
int levelSize = 1; //初始levelSize为1(第一层只有根结点)
vector<vector<int>> vv;
while (!q.empty())
{
vector<int> v; //用于存储当前层的结点值
//2、从队头取levelSize个结点放入容器v
for (int i = 0; i < levelSize; i++)
{
//取结点放入容器v
TreeNode* front = q.front();
q.pop();
v.push_back(front->val);
//若取出结点左右孩子不为空,还需将不为空的孩子结点放入队列
if (front->left) //
{
q.push(front->left);
}
if (front->right)
{
q.push(front->right);
}
}
//3、将容器v放入容器vv当中,即第该层的结点值
vv.push_back(v);
//4、更新levelSize的值为当前队列当中的元素个数
levelSize = q.size();
}
return vv; //返回层序遍历结果
}
};