层序遍历必须使用std::queue配合每层节点数计数，不可用栈或递归；密度定义需明确是实际节点数/理论最大数（2^k）还是跨度比，空节点默认不计入，计算时须用size()而非capacity()。
层序遍历必须用队列，不能用递归或栈模拟
递归天然适合深度优先，强行改写层序遍历会丢失层级边界信息；用 std::stack 模拟会导致节点顺序错乱，无法区分“第几层”。唯一可靠方式是用 std::queue 配合每层节点数计数——每次循环前记录当前队列长度，即该层真实节点数。
常见错误是只 push 子节点却不控制层数：比如在 while 循环里无条件 pop，导致下一层节点混入当前层统计。正确做法是用一个 int level_size = q.size() 锁定本层范围，再 for 循环 level_size 次。
- 初始化时若根节点非空，先 push 进队列，
level_size初始为 1 - 每 pop 一个节点，检查其
left和right，非空才 push - 每层结束后，
level_size自动更新为下一层节点总数
密度定义要明确：是节点数 / 最大可能节点数，还是节点数 / 实际宽度？
二叉树第 k 层（从 0 开始）最多有 2^k 个节点，但实际节点数常远小于此。所谓“密度”不是标准术语，必须根据需求选一种定义：
- 若关注结构紧凑性，用
density = (actual_count) / (pow(2, level))，结果在 [0,1] 区间 - 若关注该层实际占据的左右跨度（比如用于打印对齐），需额外记录每层最左、最右非空节点位置，密度可定义为
(right_pos - left_pos + 1) / (pow(2, level)) - 注意：浮点除法要强制转
double，否则整数除法结果恒为 0 或 1
示例：第 2 层（索引为 2）最多 4 个节点，若实际只有 2 个，则密度为 2.0 / 4 → 0.5，不是 2 / 4。
空节点要不要计入密度分母？取决于是否考虑完全二叉树补位
层序遍历时，常规实现只 push 非空子节点，因此队列中永远不会出现空指针；但若想统计“含空位”的密度（如评估内存浪费），就得显式插入占位符（如 nullptr），并在遍历时计数。
- 不插入空节点：密度反映真实有效节点占比，计算快，适用于大多数场景
- 插入空节点：需修改遍历逻辑——每次 pop 后，无论是否为空，都 push 其左右子（允许 push
nullptr），并用计数器区分有效/无效节点 - 性能影响明显：满二叉树下节点数翻倍，且 vector 或 queue 内存占用陡增
绝大多数业务场景（如监控树平衡度、日志分析）只需统计真实节点，nullptr 不参与任何计数和密度计算。
避免 vector 动态扩容干扰密度计算精度
有人习惯把每层节点值存进 std::vector 再算 size，这没问题；但若用 vector.push_back() 累积所有层数据，再靠索引反推每层长度，就容易出错——因为 vector 容量（capacity）可能大于大小（size），而 size() 才是真实元素数。
- 务必用
vec.size()，而非vec.capacity()计算当层节点数 - 更稳妥做法：每层用独立临时 vector，或直接用整型计数器累加，不依赖容器状态
- 如果后续要序列化输出，建议每层生成一个 vector，再统一处理，避免跨层污染
密度本身是比值，但分母若误用 capacity 就会把稀疏树算成高密度，这种 bug 很隐蔽，调试时得打日志验证每层 actual_count 和 max_possible 是否匹配。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
