如何通过队列实现二叉搜索树层序遍历的源代码逻辑？

本文共计1044个文字，预计阅读时间需要5分钟。

不是必须的，但 `std::queue` 是最自然、最不易出错的选项。它自然支持 FIFO（先进先出）顺序，接口简洁：

关键点在于：每轮循环处理「当前层全部节点」，而非「逐个节点无差别推进」。这就要求你能精确知道这一层有多少个节点——std::queue 的 size() 在进入内层循环前快照一次，就是解法核心。

如何准确记录每层节点值并分组？

不能只靠一个 while (!q.empty()) 循环到底，否则所有节点值会混成一维数组。必须在外层循环中先保存当前队列长度，再用该长度驱动内层循环。

• 每次外层循环开始时，调用 q.size() 获取当前层节点数（注意：这是快照值，后续 push() 不影响它）
• 内层循环执行恰好 size 次，每次 q.front() 取节点、q.pop() 弹出，并将左右子节点（若非空）推入队列
• 把本轮取到的节点值暂存进一个临时 std::vector<int>，结束后再 push 进结果 std::vector<std::vector<int>>

示例片段：

立即学习“C++免费学习笔记（深入）”；

std::vector<std::vector<int>> levelOrder(TreeNode* root) { std::vector<std::vector<int>> res; if (!root) return res; std::queue<TreeNode*> q; q.push(root); while (!q.empty()) { int size = q.size(); // 关键快照 std::vector<int> level; for (int i = 0; i < size; ++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; }

遇到空树或单节点时，q.size() 会不会出问题？

不会，但要主动处理空树。因为 std::queue::size() 对空队列返回 0，内层 for 循环直接跳过，res 保持空，这符合预期；但如果忘了判 if (!root) 就直接 q.push(root)，会导致对空指针解引用崩溃。

常见错误现象：Segmentation fault 或 EXC_BAD_ACCESS，往往发生在访问 node->val 或 node->left 前没检查 node 是否为空——而你的代码里 node 来自 q.front()，只要入队前都做了非空判断，这里就安全。

• 入队前必须检查：只对非空的 left 和 right 子指针调用 q.push()
• 不要在循环外初始化 level 并复用，每次外层循环都要新建 std::vector<int>
• std::queue 默认底层容器是 std::deque，无需额外指定；用 std::queue<TreeNode*> 而非 TreeNode 值类型，避免拷贝开销和析构风险

层级顺序对 BST 验证有帮助吗？

层序遍历本身不验证 BST 性质（左小右大），但它能暴露结构异常。比如你期望某层是 [10,5,15]，结果输出 [10,15,5]，说明插入逻辑可能把右子节点错挂到了左子位置。真正验证 BST 应该用中序遍历是否严格递增。

不过，在调试插入/删除后树形态时，层序输出比递归打印更直观——尤其当树退化成链表时，层序会变成单元素多行，一眼可识别高度失衡。

这时候要注意：std::queue 不提供随机访问，无法直接“跳到第 k 层”，所有层级信息必须在遍历时实时提取并保存；如果需要反复查某层，得把结果存下来再索引，别试图在遍历中途用下标去 queue 里捞。