C++如何实现二叉树的宽度优先搜索(BFS)层序遍历-C++-PHP中文网

c++中用std::queue实现bfs层序遍历最稳妥方式是外层while循环内先记录q.size()作为本层节点数，再用for循环精确处理该数量节点，每次仅push非空子节点指针，避免nullptr入队或解引用，并在每层结束后将当前层结果独立push到结果vector中。

c++如何实现二叉树的宽度优先搜索(bfs)层序遍历

用 `queue` 实现 BFS 层序遍历，核心是“每层清空队列”

直接结论：C++ 中最稳妥的方式是用 std::queue<treenode></treenode> 配合循环内嵌的 for 控制当前层节点数，而不是靠标记或双队列。否则容易漏节点、多 push 或死循环。

常见错误现象：queue 一直 pop 却没控制层数，输出变成一维扁平序列（看似对，实则无法区分层）；或者用 nullptr 做分隔符，但树含空子节点时逻辑崩溃。

每次进入外层 while 前，先记录当前 q.size()，即本层节点总数
内层 for 循环恰好执行该次数，保证只处理本层节点
每个节点出队后，仅把其非空左右子节点入队，不 push nullptr
避免用 queue 存值（如 int），必须存指针（TreeNode*），否则无法访问子节点

`TreeNode` 结构和初始化要匹配 BFS 的指针操作习惯

如果你用的是 LeetCode 风格的 TreeNode，它默认只有 val、left、right 三个成员，且构造函数不带初始化——那手动建树时极易出现悬空指针或未初始化子节点，导致 BFS 过程中访问 nullptr->left 段错误。

实操建议：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

定义时显式初始化子节点为 nullptr：TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
建树时别直接写 root->left = new TreeNode(2) 就完事，确认 root 非空
遍历时始终判断 if (node->left) 再入队，不要写 if (node->left != nullptr) —— 效果一样但前者更 C++ 习惯

需要按层分组返回？别在 BFS 过程中拼 vector，而是在每层 for 后单独 push

如果题目要求返回 vector<vector>></vector>（如 LeetCode 102），很多人会在 while 外定义一个临时 vector<int></int>，然后在内层 for 里 push_back，最后再 res.push_back(temp)。这没问题，但容易忘清空 temp 或错放位置。

更安全的写法是：每层开始前定义新 vector，for 里填，结束后直接 res.push_back({})：

vector<vector>> res;
queue<treenode> q;
q.push(root);
while (!q.empty()) {
    int size = q.size();
    vector<int> level; // 每层新建
    for (int i = 0; i val);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    res.push_back(level); // 离开 for 后立刻存
}</int></treenode></vector>

性能与边界：空树、单节点、深树的处理差异

空树（root == nullptr）是最容易忽略的边界。不做检查就直接 q.push(root)，会导致后续 q.front() 解引用空指针。单节点树则考验你是否在 for 循环里正确处理了无子节点的情况。

务必在 BFS 前加 if (!root) return {};
深树（百万级节点）下，queue 的内存增长是线性的，但频繁 push/pop 开销可控；别用 list 替代 queue，STL queue 默认基于 deque，已针对此场景优化
如果需反向层序（从底向上），不要反转结果 vector，而应在每层处理完后用 res.insert(res.begin(), level) —— 虽然 O(n) 插入，但比最后 reverse 更直观，也避免混淆层级顺序