目录
题目
给你二叉树的根节点 root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]]
示例 2:
输入:root = [1] 输出:[[1]]
示例 3:
输入:root = [] 输出:[]
提示:
- 树中节点数目在范围
[0, 2000]
内 -1000 <= Node.val <= 1000
思路
二叉树层序遍历的特点就是从上往下从左往右,依次一层一层去遍历,所以需要吧每一层都存入一个数组中,然后将数组同一存入一个vector中,通俗理解就是我们所熟悉的二维数组,所以在对二叉树进行遍历时就需要通过两个条件来进行划分,一是当前在第几层,二是当前层还有几个元素没有处理。而结合层序遍历的特点,我们就可以利用queue栈来进行操作,从根节点开始,先进先出,定义一个levelnum来判断当前层有几个元素需要写入,从左到右每个元素写入完成后将left和right再插入到队尾,当levelnum==0时说明当前层的元素已经全部处理完毕,而此时下一层需要处理的元素也都全部进入队列,这时将队列中的元素赋值给levelnum进行更新。然后继续如上的操作直到队列为空。
/**
* 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)
{
vector<vector<int>> ret;
int levelnum=0;
queue<TreeNode*> q;
if(root)//将根节点放入队列中
{
q.push(root);
levelnum=1;
}
while(!q.empty())//判空
{
vector<int> v;
while(levelnum--)//levelnum控制一层一层的出
{
TreeNode* front=q.front();//取出队列中第一个元素
q.pop();
v.push_back(front->val);//插入当前层的vector
//带入下一层节点
if(front->left) q.push(front->left);
if(front->right) q.push(front->right);
}
ret.push_back(v);
levelnum=q.size();
}
return ret;
}
};