层序遍历：BFS核心技巧

一、什么是层序遍历层序遍历按照从上到下、每一层从左到右依次访问节点。本质就是广度优先搜索 BFS借助队列 queue实现。递归是深度优先 DFS队列迭代是广度优先 BFS。二、核心思路把根节点入队每次统计当前队列元素个数当前层节点数循环取出当前层所有节点取出节点后先左后右把孩子入队逐层往下直到队列为空三、层序遍历基础模板打印版#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; queueTreeNode* 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; vectorvectorint levelOrder(TreeNode* root) { vectorvectorint res; if(!root) return res; queueTreeNode* q; q.push(root); while(!q.empty()) { int size q.size(); vectorint 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六、层序遍历经典适用题型二叉树层序遍历、按层输出二叉树最大深度、最小深度二叉树右视图、左视图二叉树每层平均值二叉树之字形遍历七、DFS 递归 vs BFS 队列 一句话区别DFS 前中后序一路往深走用递归 / 栈BFS 层序遍历一层一层走用队列八、新手易错点不记录size无法区分每一层孩子入队顺序写反先右后左根节点为空不特判直接入队崩溃混淆深度优先和广度优先使用场景九、今日总结层序遍历 BFS 广度优先依赖队列实现固定套路取每层 size → 遍历当前层 → 孩子入队记住两套模板简单打印版、二维数组分层版层序是解决二叉树层级类题目万能套路