C++如何实现二叉树的层序遍历_C++使用队列实现树的广度优先【算法】

层序遍历必须用队列而非栈，因其需FIFO保证“从上到下、从左到右”逐层访问；栈的LIFO会导致深度优先式乱序，且易引发死循环或层数错位。

为什么层序遍历必须用队列，不能用栈

因为层序遍历要求“从上到下、从左到右”逐层访问节点，本质是先进先出（FIFO）——新一层的子节点必须等当前层所有节点处理完才能开始访问。栈是后进先出（LIFO），会把刚压入的右子节点优先弹出，导致顺序变成“根→右→左→右子树的右……”，实际跑出来是深度优先的变种，不是层序。

常见错误现象：std::stack 实现时输出顺序乱、层数错位、甚至死循环（尤其有重复指针或空指针未判时）。

• 队列保证同一层节点在队首连续排列，front() 取出后 pop()，再把它的左右子节点 push() 到队尾
• 每轮循环前记录 q.size()，用于控制本轮只处理“当前层”的节点数，避免新入队的下层节点干扰计数
• 空指针必须跳过：遇到 nullptr 不能调用 left/right，也不能入队

标准实现中如何正确分层输出

如果题目要求返回二维 vector（每层一个子 vector），关键不在遍历逻辑，而在“什么时候切层”。不能靠节点值判断，也不能依赖父子关系标记；唯一可靠依据是每轮循环开始时队列中剩余的节点数——它恰好等于当前待处理层的宽度。

示例片段：

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

Pebblely

AI产品图精美背景添加

下载

vector> levelOrder(TreeNode* root) {
    if (!root) return {};
    vector> res;
    queue q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size(); // 记录本层节点总数
        vector 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;
}

• size = q.size() 必须在 for 循环外获取，否则每次 q.size() 都在变，循环次数失控
• 不要在 for 内部写 if (q.empty()) break —— 层内不可能中途为空
• 如果只要一维结果（不区分层），直接用单个 vector 接收 node->val 即可，无需嵌套

使用 std::queue 时容易忽略的类型与内存细节

队列里存的是 TreeNode*（指针），不是 TreeNode 对象本身。这是性能和正确性的双重需要：复制节点开销大，且会导致子树丢失（深拷贝需额外实现，浅拷贝则 left/right 指针失效）。

• 若误写成 queue，编译可能通过但运行时行为异常（如访问已析构临时对象的成员）
• 不需要手动 delete 指针——题设树内存由调用方管理，你只负责读；释放操作属于构造/销毁逻辑，不在遍历职责内
• 在 LeetCode 等平台，输入树由 OJ 构造，确保所有指针合法或为 nullptr；本地测试时若自己建树，务必检查 new 是否成功、是否漏掉 nullptr 初始化

遇到空树或单节点时的边界行为验证

很多实现在线上 AC 却本地崩溃，问题常出在没覆盖 root == nullptr 或只有 root 无子节点的情况。这些不是“特殊情况”，而是算法起点。

• root == nullptr → 直接返回空容器，不可对 q.front() 或 node->val 解引用
• root 存在但 left 和 right 均为 nullptr → 队列第二轮变空，循环自然退出，无需额外判断
• 调试时可在循环内加 cout 辅助观察分层节奏，比单步看队列更直观

真正容易被忽略的是：当某层节点全部没有子节点时，队列清空，但代码逻辑已天然处理完毕——不必补 return，也不必设 flag。广度优先的终止条件永远只是队列为空，不依赖节点内容。