Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:Given binary tree [3,9,20,null,null,15,7]
/ \
/ \
return its level order traversal as:
[
[],
[,],
[,]
]
二叉树的层次遍历使用队列来实现，很大程度上类似于求树的最大深度。
第一种解法：开始时当前结点数curLevelCount=1,nextLevelCount=0,根据curLevelCount来输入每一层的结点值，当其左右子树存在时，将左右子树存入队列，并nextLevelCount++，每弹出一个当前层的结点时，curLevelCount--，当其为0时，再创建一个新的vector。
C++：
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res={};
queue<TreeNode*> q;
if(!root)
return res;
q.push(root);
int curLevelCount=,nextLevelCount=;
vector<int> temp={};
while(!q.empty()){
TreeNode* cur=q.front();
temp.push_back(cur->val);
q.pop();
curLevelCount--;
if(cur->left){
q.push(cur->left);
nextLevelCount++;
}
if(cur->right){
q.push(cur->right);
nextLevelCount++;
}
if(curLevelCount==){
res.push_back(temp);
temp={};
curLevelCount=nextLevelCount;
nextLevelCount=;
}
}
return res;
}
第二种方法不用参数计算每一层结点个数，利用for循环，每一层时利用队列的大小来计算每一层的结点数。两层循环嵌套，效率比较低。
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res={};
queue<TreeNode*> q;
if(!root)
return res;
q.push(root);
while(!q.empty()){
vector<int> temp={};
for(int i=q.size();i>;i--){
TreeNode* cur=q.front();
temp.push_back(cur->val);
q.pop();
if(cur->left)
q.push(cur->left);
if(cur->right)
q.push(cur->right);
}
res.push_back(temp);
}
return res;
}