二叉树层序遍历

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]
]提示:
0 <= 二叉树的结点数 <= 1500/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;* };*/
class Solution {
public:/*** * @param root TreeNode类 * @return int整型vector<vector<>>*/vector<vector<int> > levelOrder(TreeNode* root) {// write code here  }
};

在这里插入图片描述

由输出样例可以看出，每一层的结点都用一个vector来存的；

比如第一层：用一个vector来存[3];

第二层，用一个vector[9,20];

第三层，用一个vector[15,7].

这样的话，我们就一层一层的遍历，相较于普通的层序遍历，普通的层序遍历在 ==while（队列不空）==循环里面，是每次pop()一个结点的。（不知道这个能不能想明白），我们在这里，我们在==while（队列不空）==这个循环里面就一层一层的pop(),这样就可以记录每一层的了。

先这样想，看看代码就懂了；

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;* };*/class Solution {
public:/*** * @param root TreeNode类 * @return int整型vector<vector<>>*/vector<vector<int> > levelOrder(TreeNode* root) {// write code herevector<vector<int> > ans;//空的if ( root == NULL ) return ans;//队列queue<TreeNode*> q;q.push(root);//队列不空while ( !q.empty() ) {int size = q.size();//记录当前一层的个数vector<int> v;while (size--) { //把一层的全部pop,再把下一层加进来TreeNode *temp = q.front();q.pop();v.push_back(temp->val);//把下一层的结点入队if ( temp->left ) q.push(temp->left);if ( temp->right ) q.push(temp->right); }if ( v.size() ) ans.push_back(v);}return ans;}
};