力扣刷题——二叉树的层序遍历

题目链接：二叉树的层序遍历

题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

题目分析

二叉树的层序遍历对于C++而言还是比较好处理的，用一个队列容器存放每层的各个节点，然后不断出各个节点并入他们的子节点即可。这题的难度主要在于除了层序遍历以外，需要用一个二维数组来存放每层中的节点的值。这就意味着需要标识二叉树每层中节点的个数。这里可以使用一个整型变量来存放每层节点的个数，以此作为每层循环结束的标识，具体代码如下：

代码实现

vector<vector<int>> levelOrder(TreeNode* root) 
{
    
	vector<vector<int>> ret;
	queue<TreeNode*> q;//存放每层的各个节点指针
	if (root)
	{
    
		q.push(root);
	}
	int levelsize = q.size();
	while (!q.empty())
	{
    
		vector<int> tmp;
		while (levelsize)
		{
    
			TreeNode* cur = q.front();
			q.pop();
			tmp.push_back(cur->val);
			if (cur->left)
			{
    
				q.push(cur->left);
			}
			if (cur->right)
			{
    
				q.push(cur->right);
			}
			levelsize--;
		}
		ret.push_back(tmp);
		levelsize = q.size();//每一层元素个数
	}
	return ret;

}