二叉树宽度最大值是指所有层中节点数最多的一层的节点个数；不能只靠dfs递归，因其无法保证同层节点集中处理，易混淆或遗漏，必须用bfs层序遍历逐层快照队列大小来准确统计。
什么是二叉树宽度最大值，为什么不能只靠递归深度遍历
二叉树的“宽度”指某一层上节点的总数，宽度最大值就是所有层中节点数最多的一层的节点个数。很多人第一反应是用 DFS 递归记录每层节点数，但问题在于：DFS 天然不保证同一层节点被集中处理，容易把不同子树的同层节点计数混在一起，或者漏掉空位（比如 nullptr 不代表该位置无节点，而是该分支不存在）——而宽度统计**只算真实存在的节点**，不补空位，也不依赖满二叉树结构。
真正可靠的做法是层序遍历（BFS），逐层展开、逐层计数。哪怕树退化成链表（单边延伸千万层），只要内存够存队列，就能正确统计每一层的 size()。
用 std::queue 做层序遍历并实时更新最大宽度
核心逻辑是每次循环前先记录当前队列长度，这个长度就是本层节点总数；然后用一个固定次数的内层循环把这一层全部出队，并将它们的非空子节点入队。这样能严格隔离层级。
- 必须用
int currentLevelSize = q.size()快照当前层大小，不能在循环中反复调用q.size()，因为队列在变化 - 入队前务必判空：
if (node->left)而不是if (node->left != nullptr)（后者冗余，且 C++11 后if (node->left)更惯用） - 初始时若根节点为
nullptr，直接返回0，避免队列为空却进入循环
int maxWidth(TreeNode* root) {
if (!root) return 0;
std::queue<treenode> q;
q.push(root);
int maxWidth = 0;
while (!q.empty()) {
int levelSize = q.size(); // 关键快照
maxWidth = std::max(maxWidth, levelSize);
for (int i = 0; i left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return maxWidth;
}</treenode>
遇到极端不平衡树时，std::queue 的内存和性能表现如何
最坏情况是树完全倾斜（如只有右子节点），此时队列峰值大小恒为 1，空间 O(1)；而最宽情况是满二叉树第 h 层，队列峰值达 O(2^h)，但这是宽度本身的定义决定的，无法规避。真正要注意的是：不要用 std::vector 模拟队列（比如每次 erase(begin())），那会把单次出队变成 O(n)，整体退化到 O(n²)。
-
std::queue底层默认用std::deque，push/pop 均摊 O(1) - 如果编译器支持 C++17 及以上，可考虑用
std::queue<treenode std::vector>></treenode>强制用 vector 作容器，但需手动保证 pop 时不移动内存（实际仍推荐默认 deque） - 不需要存储层号或节点索引，除非题目要求“最宽层的编号”，否则纯计数即可
为什么不用数组下标模拟（类似堆式存储）来算宽度
有人想套用完全二叉树的数组索引规律（根在 0，左子在 2*i+1，右子在 2*i+2），但这只对**物理连续存储的完全二叉树**有效。普通二叉树节点在内存中地址离散，没有隐含索引关系；强行编号会导致大量无效索引和越界风险，且无法反映真实宽度（比如某层只有最左和最右两个节点，中间全空，宽度仍是 2，不是索引差+1）。
所以只要不是题目明确限定“输入是完全二叉树的数组表示”，就别碰下标模拟。老老实实 BFS 最稳。
宽度最大值的本质是层节点数的极值，不是位置跨度。队列一次清空一层，比任何数学推导都直接可靠。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
