C++实现二叉树的宽度优先搜索BFS _ 队列与层级记录【源码】-C++-PHP中文网

std::queue是bfs最自然的选择，因其fifo特性完美匹配“逐层扩展”逻辑；需用q.size()冻结每层节点数以保层级信息，访问treenode指针前必须判空防崩溃。

c++实现二叉树的宽度优先搜索bfs _ 队列与层级记录【源码】

为什么 `std::queue` 是 BFS 最自然的选择

因为 BFS 本质就是“一层层往外扩”，而队列的 FIFO 特性天然匹配这个过程：先入队的节点，一定先被访问、先扩展子节点。用栈或 vector 模拟反而容易错乱层级顺序。

常见错误是把 root 入队后，直接 while (!q.empty()) { auto n = q.front(); q.pop(); ... } 就完事——这样能遍历所有节点，但**完全丢失层级信息**，无法回答“第 k 层有哪些节点”或“每层最大值是多少”这类问题。

实操建议：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

始终用 std::queue<treenode></treenode>（指针，避免拷贝树节点）
每次循环开始前，用 q.size() 记录当前层节点数，再循环 pop 这么多次，确保“处理完一层才进下一层”
不要在循环中动态修改 q.size() 的判断依据（比如写成 i 且在循环内 push —— <code>size() 会变，导致逻辑错乱）

如何正确记录每一层的节点值（含空节点处理）

很多实现只存非空子节点，导致层级对齐失败；但若严格按满二叉树补 nullptr，又浪费空间。实际取舍取决于需求：

如果目标是打印层级结构（如 LeetCode 的 levelOrder），只需保存非空节点；如果要做“之字形遍历”或“检查是否为完全二叉树”，就得显式处理空位。

实操建议：

标准层级遍历（忽略空节点）：只对 node->left 和 node->right 非空时才 push
需要空占位时：在每层末尾不补空，而是在子节点入队前统一判断，if (node) { q.push(node->left); q.push(node->right); } else { q.push(nullptr); q.push(nullptr); } —— 但注意这会导致无限 nullptr，必须加层数限制或空节点计数终止
更稳妥的做法是用两个队列轮换，或用 pair 存 {node, level}，避免歧义

`TreeNode` 结构定义与空指针安全访问

标准 TreeNode 定义里 left 和 right 是裸指针，BFS 过程中任何一次解引用都可能 crash。尤其在调试时临时插入 cout val 却忘了判空，就会触发 segmentation fault。

实操建议：

定义时明确初始化： TreeNode() : val(0), left(nullptr), right(nullptr) {}
每次访问 node->left 或 node->val 前，先写 if (!node) continue;（放在循环开头比分散判空更可靠）
用智能指针（如 std::unique_ptr<treenode></treenode>）可提升安全性，但 LeetCode 等平台输入固定为裸指针，实际项目中才建议切换
错误现象示例：member access within null pointer of type 'struct TreeNode' —— 这是编译器（如 clang）的 UB 提示，说明你解引用了 nullptr

完整可运行的层级遍历代码（带注释）

以下是最简可用版本，返回二维 vector，每行是一个层级的节点值：

vector<vector>> levelOrder(TreeNode* root) {
    vector<vector>> res;
    if (!root) return res;
<pre class="brush:php;toolbar:false;">queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
    int levelSize = q.size(); // 关键：冻结当前层宽度
    vector<int> level;
    for (int i = 0; i < levelSize; ++i) {
        TreeNode* node = q.front();
        q.pop();
        level.push_back(node->val);
        if (node->left)  q.push(node->left);
        if (node->right) q.push(node->right);
    }
    res.push_back(level);
}
return res;

}

注意 levelSize 必须在 for 循环外获取，且不能写成 for (int i = 0; i —— 因为循环体内 <code>push 会让 q.size() 动态增长，导致多处理下一层的节点。

真正容易被忽略的是：当树极深时，queue 的内存占用是 O(w)，w 是最大层宽，不是树高。对倾斜树（如只有右链），BFS 的空间开销反而比 DFS 小；但对满二叉树，BFS 在最后一层会存下 ~n/2 个节点，务必确认内存约束。