目录
题目
思路
题目
给你二叉树的根节点 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;}
};
