【二叉树的广度优先遍历BFS---队列实现】

有一个问题：用两个数组也可以做，为什么要用队列呢？

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; } };