有一个问题：用两个数组也可以做，为什么要用队列呢？
BFS的遍历规则：（一层一层按顺序进行遍历）
1.先访问根节点
2.再访问第二层的节点从左到右依次
3.第三层...
核心：先遇到的节点先进行处理，和队列的特性（FIFO）十分匹配
实现思路：先让根节点入队，再取出队首出队进行处理，再把左右子节点入队 一次弹出进行处理
我们练习一下：
题目：给你二叉树的根节点root，返回其节点值的层序遍历。 （即逐层地，从左到右访问所有节点）。
/** * 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) { if(root==nullptr)return {}; vector<vector<int>>ans; queue<TreeNode*>q; q.push(root); while(!q.empty()){ vector<int> vals; for(int n=q.size();n>0;n--){ auto node=q.front(); q.pop(); vals.push_back(node->val); if(node->left) q.push(node->left); if(node->right) q.push(node->right); } ans.push_back(move(vals)); } return ans; } };