【二叉树的广度优先遍历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: vectorvectorint levelOrder(TreeNode* root) { if(rootnullptr)return {}; vectorvectorintans; queueTreeNode*q; q.push(root); while(!q.empty()){ vectorint vals; for(int nq.size();n0;n--){ auto nodeq.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; } };