C++实现二叉树的层序遍历及深度统计 _ 队列结构实现逻辑【实战】-C++-PHP中文网

应使用 std::queue 而非手写链表，因其 push/front/pop 均为 O(1)、底层基于 std::deque 且内存局部性好；手写链表易出现指针错误，且无必要重复造轮子。

c++实现二叉树的层序遍历及深度统计 _ 队列结构实现逻辑【实战】

为什么用 `std::queue` 而不是手写链表做层序遍历

因为 std::queue 的 push() 和 front()/pop() 操作都是 O(1)，且底层通常基于 std::deque，内存局部性好；手写链表容易在指针管理上出错，比如漏删节点或重复释放。实际项目里，除非有特殊内存约束（如嵌入式场景禁止 STL），否则直接用 std::queue 更稳。

注意：必须存指针（TreeNode*），不能存 TreeNode 值对象——否则会触发拷贝构造，二叉树结构丢失，还可能栈溢出。

`queue.size()` 在循环中要“快照”一次

层序遍历时，常需按层处理（比如统计每层节点数、找每层最大值）。这时不能在 while (!q.empty()) 里直接用 q.size() 控制内层循环，因为 q.size() 是实时变化的。

错误写法：for (int i = 0; i —— 每次调用 q.size() 都返回当前长度，循环次数会变
正确写法：先 int levelSize = q.size();，再 for (int i = 0; i

这个细节一漏，遍历就乱序，深度统计结果偏小，调试时很难定位。

深度统计别只靠 `while` 循环次数

仅靠外层 while (!q.empty()) 的循环次数算深度，只适用于「完全二叉树」或「所有叶子都在最底层」的情况。真实二叉树可能左右子树高度差很大，必须结合节点层级信息。

C++14

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

下载

推荐做法：每个入队节点附带其深度，用 std::queue<:pair int>> 或封装结构体。例如：

queue<pair int>> q;
q.push({root, 1});
while (!q.empty()) {
    auto [node, depth] = q.front(); q.pop();
    maxDepth = max(maxDepth, depth);
    if (node->left) q.push({node->left, depth + 1});
    if (node->right) q.push({node->right, depth + 1});
}
</pair>

如果只关心最大深度，不关心每层内容，其实 DFS 更简洁；但题目明确要求「层序遍历」+「深度统计」，那就得在 BFS 过程中带深度状态走。