二叉树层序遍历（BFS）完全指南：从基础到实战

一、层序遍历核心概念

1.1 什么是层序遍历？

层序遍历（Level Order Traversal）是一种广度优先搜索（BFS）算法，它按照树的层次，从上到下、从左到右逐层访问每个节点。

示例二叉树： 1 ← 第1层 / \ 2 3 ← 第2层 / \ \ 4 5 6 ← 第3层 层序遍历结果：[[1], [2, 3], [4, 5, 6]] 访问顺序：1 → 2 → 3 → 4 → 5 → 6

1.2 与深度优先搜索（DFS）对比

二、基础层序遍历实现

2.1 基本实现（返回一维数组）

// 基本层序遍历：返回所有节点的值（不区分层次）vector<int>levelOrderSimple(TreeNode*root){vector<int>result;if(!root)returnresult;queue<TreeNode*>q;// 核心数据结构：队列q.push(root);while(!q.empty()){TreeNode*node=q.front();// 1. 取队首q.pop();// 2. 出队result.push_back(node->val);// 3. 处理当前节点// 4. 将子节点入队（先左后右）if(node->left)q.push(node->left);if(node->right)q.push(node->right);}returnresult;}// 示例树输出：[1, 2, 3, 4, 5, 6]

2.2 分层存储的实现（返回二维数组）

// 分层存储的层序遍历：每层一个子数组vector<vector<int>>levelOrder(TreeNode*root){vector<vector<int>>result;if(!root)returnresult;queue<TreeNode*>q;q.push(root);while(!q.empty()){intlevelSize=q.size();// 关键：记录当前层节点数vector<int>currentLevel;// 处理当前层的所有节点for(inti=0;i<levelSize;i++){TreeNode*node=q.front();q.pop();currentLevel.push_back(node->val);// 将下一层节点入队if(node->left)q.push(node->left);if(node->right)q.push(node->right);}result.push_back(currentLevel);// 将当前层加入结果}returnresult;}// 示例树输出：[[1], [2, 3], [4, 5, 6]]

三、层序遍历执行过程详解

3.1 执行过程可视化

树结构： 1 / \ 2 3 / \ \ 4 5 6 执行过程追踪表： | 循环 | 队列内容 | 当前层大小 | 当前处理节点 | 操作 | 当前结果层 | |------|-----------------|------------|--------------|---------------------|--------------| | 初始 | [1] | - | - | 初始化 | [] | | 1 | [1] | 1 | 1 | 处理1，入队2、3 | [1] | | | [2, 3] | | | 完成第1层 | | | 2 | [2, 3] | 2 | 2 | 处理2，入队4、5 | [2] | | | [3, 4, 5] | | 3 | 处理3，入队6 | [2, 3] | | | [4, 5, 6] | | | 完成第2层 | | | 3 | [4, 5, 6] | 3 | 4 | 处理4，无子节点 | [4] | | | [5, 6] | | 5 | 处理5，无子节点 | [4, 5] | | | [6] | | 6 | 处理6，无子节点 | [4, 5, 6] | | | [] | | | 完成第3层 | | 最终结果：[[1], [2, 3], [4, 5, 6]]

3.2 队列状态变化图

时间轴： t0 → t1 → t2 → t3 队列： [1] → [2,3] → [4,5,6] → [] ↓ ↓ ↓ ↓ 处理： 1 2 → 3 4 → 5 → 6 完成 层次： 第1层 第2层 第3层

四、层序遍历的常见变种

4.1 自底向上层序遍历

// 从底层到顶层的层序遍历vector<vector<int>>levelOrderBottom(TreeNode*root){vector<vector<int>>result;if(!root)returnresult;queue<TreeNode*>q;q.push(root);while(!q.empty()){intlevelSize=q.size();vector<int>currentLevel;for(inti=0;i<levelSize;i++){TreeNode*node=q.front();q.pop();currentLevel.push_back(node->val);if(node->left)q.push(node->left);if(node->right)q.push(node->right);}// 关键区别：每次插入到结果的开头result.insert(result.begin(),currentLevel);}returnresult;}// 示例树输出：[[4, 5, 6], [2, 3], [1]]

4.2 锯齿形层序遍历（Z字形遍历）

// 锯齿形层序遍历：一层从左到右，下一层从右到左vector<vector<int>>zigzagLevelOrder(TreeNode*root){vector<vector<int>>result;if(!root)returnresult;queue<TreeNode*>q;q.push(root);boolleftToRight=true;// 方向标志while(!q.empty()){intlevelSize=q