层序遍历：BFS核心技巧

一、什么是层序遍历

层序遍历：按照从上到下、每一层从左到右依次访问节点。本质就是广度优先搜索 BFS，借助队列 queue实现。

递归是深度优先 DFS；队列迭代是广度优先 BFS。

二、核心思路

1. 把根节点入队
2. 每次统计当前队列元素个数（当前层节点数）
3. 循环取出当前层所有节点
4. 取出节点后，先左后右把孩子入队
5. 逐层往下，直到队列为空

三、层序遍历基础模板（打印版）

#include <iostream> #include <queue> using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 层序遍历 BFS void levelOrder(TreeNode* root) { if(!root) return; queue<TreeNode*> q; q.push(root); while(!q.empty()) { // 当前层节点数量 int size = q.size(); for(int i = 0; i < size; ++i) { TreeNode* cur = q.front(); q.pop(); cout << cur->val << " "; // 左孩子入队 if(cur->left) q.push(cur->left); // 右孩子入队 if(cur->right) q.push(cur->right); } } }

四、LeetCode 标准模板（分层存二维数组）

很多题目要求按层保存结果，返回二维 vector，刷题必备：

#include <vector> #include <queue> using namespace std; vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; if(!root) return res; queue<TreeNode*> q; q.push(root); while(!q.empty()) { int size = q.size(); vector<int> layer; for(int i = 0; i < size; ++i) { TreeNode* cur = q.front(); q.pop(); layer.push_back(cur->val); if(cur->left) q.push(cur->left); if(cur->right) q.push(cur->right); } res.push_back(layer); } return res; }

五、完整测试代码

int main() { // 构建二叉树 TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); cout << "层序遍历："; levelOrder(root); return 0; }

输出：

1 2 3 4 5

六、层序遍历经典适用题型

1. 二叉树层序遍历、按层输出
2. 二叉树最大深度、最小深度
3. 二叉树右视图、左视图
4. 二叉树每层平均值
5. 二叉树之字形遍历

七、DFS 递归 vs BFS 队列 一句话区别

• DFS 前中后序：一路往深走，用递归 / 栈
• BFS 层序遍历：一层一层走，用队列

八、新手易错点

1. 不记录size，无法区分每一层
2. 孩子入队顺序写反：先右后左
3. 根节点为空不特判，直接入队崩溃
4. 混淆深度优先和广度优先使用场景

九、今日总结

1. 层序遍历 = BFS 广度优先，依赖队列实现
2. 固定套路：取每层 size → 遍历当前层 → 孩子入队
3. 记住两套模板：简单打印版、二维数组分层版
4. 层序是解决二叉树层级类题目万能套路