c++实现二叉树bfs层序遍历需用std::queue存指针，每轮先快照q.size()固定本层节点数，再循环处理并入队非空子节点；空树或nullptr子节点必须显式跳过，避免解引用崩溃。
用 queue 实现 BFS 层序遍历，核心是“队列存节点指针”
直接用 std::queue<treenode></treenode>，不是存值也不是存拷贝。二叉树节点通常动态分配，TreeNode* 才能避免复制开销和悬空指针。每次从队首取一个节点，把它的左右子节点（非空）推入队尾——这就是层序扩展的本质。
常见错误是误用 queue<treenode></treenode>，导致编译失败（TreeNode 无默认构造/拷贝构造）或运行时崩溃（浅拷贝后析构原节点）。C++ 中绝大多数树遍历都应操作指针或智能指针。
- 确保
TreeNode定义含left和right成员，类型为TreeNode* - 入队前必须判空：
if (node->left) q.push(node->left); - 不要在循环中修改队列大小（如误调
q.size()后再循环时队列被 push，导致无限循环）
按层分组输出：用当前层节点数控制内层循环
如果需要每层单独一个 vector（比如返回 vector<vector>></vector>），不能靠 while (!q.empty()) 简单展开。必须在每轮外层循环开始时记录当前队列长度，即本层节点总数。
这个长度是“快照”，后续 push 不会影响它。否则边 pop 边 push，q.size() 动态变化，会导致某层节点被错分到下一层。
vector<vector>> levelOrder(TreeNode* root) {
if (!root) return {};
vector<vector>> res;
queue<treenode> q;
q.push(root);
while (!q.empty()) {
int n = 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);
}
return res;
}
</int></treenode></vector></vector>
遇到 nullptr 节点怎么办？标准 BFS 不处理空指针
层序遍历本身不接受 nullptr 作为有效节点。如果你的输入里有显式 nullptr 子节点（比如 LeetCode 的序列化格式），它们只是占位符，不应入队。代码里已通过 if (node->left) 这类判断自然跳过。
若强行把 nullptr 推入 queue<treenode></treenode>，后续 q.front()->val 会触发段错误。BFS 的安全边界就是“只处理非空指针”，这点比 Python 的 None 检查更硬性。
- 不要写
q.push(nullptr)，除非你明确要标记层结束（此时需额外逻辑区分） - LeetCode 输入中的
null是序列化概念，反序列化后对应的就是跳过该分支，不是运行时要塞进队列的对象 - 调试时可加断言：
assert(node != nullptr);放在q.front()取出后立刻检查
性能与内存：为什么不用 deque 或 list？
std::queue 默认底层是 std::deque，但你不需要直接操作 deque 接口。仅需 push/front/pop 三个操作，queue 封装足够且语义清晰。换成 list 或手写链表反而增加 cache miss 和内存碎片。
真正影响性能的是节点分配方式：如果树由大量 new TreeNode 构建，频繁堆分配会拖慢；若用对象池或 std::vector 预分配节点，则 BFS 本身几乎无额外开销。遍历复杂度始终是 O(n)，但常数项取决于内存局部性。
容易被忽略的是：BFS 最坏空间复杂度是 O(w)，w 为最大层宽。对于完全二叉树，最后一层节点数接近 n/2，队列可能占用大量内存——这比递归 DFS 的栈空间更隐蔽，尤其在嵌入式或内存受限场景下得留意。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
