c++oding="utf-8" ?>
用std::queue实现bfs遍历二叉树需先判空根节点，每次取队首并入队非空子节点；按层输出需在while循环内快照q.size()控制for循环次数；须严格避免解引用nullptr，入队前和出队后均应判空。
用 queue 实现 BFS 遍历二叉树
直接用 std::queue 存节点指针，按层推进即可。不需要递归，也不依赖栈，核心就是“先进先出”——每次取队首，把它的左右子节点（如果非空）推入队尾。
常见错误是漏判空指针：如果根节点为 nullptr，必须提前返回，否则 queue.push(nullptr) 后在循环里解引用会崩溃。
- 初始化时只 push 非空根节点
- 循环中每次 pop 后立即检查是否为空（虽然正常流程不会出现，但防御性写法更稳）
- 子节点入队前必须判空：
if (node->left) q.push(node->left);
如何按层分组输出（例如每层一个 vector）
关键在每次 while 循环开始时记录当前队列长度，即本层节点数。用 for 循环精确处理这一层，避免和下一层混在一起。
示例逻辑：
while (!q.empty()) {
int level_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);
}
result.push_back(level);
}</int>
注意：q.size() 在 for 循环内不能当条件用（因为队列在增长），必须提前快照。
BFS 中访问顺序与内存布局的关系
二叉树本身没有连续内存布局，BFS 的顺序完全由入队时机决定，和物理地址无关。但实际性能受 cache 友好性影响：如果节点是 new 出来的，分散在堆上，频繁跳转可能引发 cache miss。
若对性能敏感（比如海量节点），可考虑：
- 用对象池或 arena 分配器集中管理节点内存
- 避免在 BFS 过程中动态 new/delete，改用预分配数组 + 索引模拟指针
- 确认编译器没对
queue做过度优化（如 libc++ 的queue底层是deque，比list更 cache 友好）
遇到 nullptr 成员时的典型 crash 场景
最常发生在未检查子节点就直接访问：q.push(node->left) 而 node->left 是 nullptr —— 这本身不 crash，但后续 pop 出来后调用 node->val 或 node->left 就会段错误。
正确做法只有两个位置需要判空：
- 入队前：
if (node->left) q.push(node->left); - 出队后、解引用前：虽然按逻辑不会 pop 到
nullptr，但加一句if (!node) continue;是低成本防御
别在构造 queue 时塞 nullptr，也别靠 try-catch 捕获 segfault——C++ 里这不算异常，是未定义行为。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
