程序填空题：二叉树的层次遍历

层次遍历二叉树，从上往下，每层从左往右。本题用queue来解决BFS问题，输出层次遍历的结果。

c++
#include <iostream>
#include <queue>

using namespace std;
struct TreeNode
{
int val;
TreeNode *left,*right;
TreeNode(int x):
val(x),left(NULL),right(NULL)
{}
};

class Solution
{
public:
void bfs(TreeNode *root)//返回的是一个int的vector
{
queue<TreeNode *>q;//辅助队列

if(root==NULL)
return;

q.push(@@[root](3));

while(@@[!q.empty()](3))
{
cout<<q.front()->val<<" ";
if(q.front()->left!=NULL)
{
q.push(@@[q.front()->left](3));
}
if(q.front()->right!=NULL)
{
q.push(q.front()->right);
}
@@[q.pop()](3);//弹出第一个元素
}
return;
}
};

int main()
{
Solution sol;
//初始化一棵树
TreeNode* root = new TreeNode(8);
TreeNode* b1 = new TreeNode(6);
TreeNode* b2 = new TreeNode(10);
TreeNode* c1 = new TreeNode(5);
TreeNode* c2 = new TreeNode(7);
TreeNode* c3 = new TreeNode(9);
TreeNode* c4 = new TreeNode(1);

root->left = b1;
root->right = b2;

b1->left = c1;
b1->right = c2;
b2->left = c3;
b2->right = c4;

sol.bfs(root);

return 0;
}







答案：
第1空：root

第2空：!q.empty()

第3空：q.front()->left

第4空：q.pop()