垂直宽度是树中所有节点在垂直列上的最大列号差加1；列号规则为根节点为0，左子节点减1、右子节点加1，通过BFS遍历时动态更新最小/最大列号计算。
什么是垂直宽度？列号怎么定义
垂直宽度不是树的高度或节点总数，而是所有节点在“垂直列”上的最大列号差。关键在于列号分配规则：根节点列号为 0；左子节点列号 = 父节点列号 − 1；右子节点列号 = 父节点列号 + 1。同一列的节点在垂直方向对齐（比如 root->left->right 和 root->right->left 可能同列）。
列号本身会随树深度线性发散，不能直接用深度控制。实际计算中，不需要预先知道列范围，更稳妥的做法是边遍历边记录最小/最大列号。
用 BFS + 列号映射最直观可靠
BFS 天然按层推进，每个节点携带当前列号，避免递归栈深问题，也方便统一更新全局列边界。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 每个队列元素用
std::pair<TreeNode*, int>存储节点指针和对应列号 - 初始化：入队
{root, 0}，minCol = 0，maxCol = 0 - 出队时更新：
minCol = std::min(minCol, col)，maxCol = std::max(maxCol, col) - 左子入队用
col - 1，右子用col + 1 - 最终宽度 =
maxCol - minCol + 1（+1 是因为列号是离散整数，含端点）
int verticalWidth(TreeNode* root) {
if (!root) return 0;
std::queue<std::pair<TreeNode*, int>> q;
q.push({root, 0});
int minCol = 0, maxCol = 0;
while (!q.empty()) {
auto [node, col] = q.front(); q.pop();
minCol = std::min(minCol, col);
maxCol = std::max(maxCol, col);
if (node->left) q.push({node->left, col - 1});
if (node->right) q.push({node->right, col + 1});
}
return maxCol - minCol + 1;
}
DFS 实现要注意列号传递和初始化陷阱
DFS 更节省空间，但容易漏掉某分支未更新 minCol/maxCol，尤其当只用局部变量传参时。
立即学习“C++免费学习笔记（深入）”；
- 必须用引用或全局变量维护
minCol和maxCol，否则每层递归的修改不累积 - 初始调用必须设
minCol为极大值、maxCol为极小值（如INT_MAX/INT_MIN），不能设为 0 - 不推荐用
std::map先存每列节点再取 key 范围——额外空间 O(n)，且 map 插入有 log n 开销，纯属绕路
空树、单节点、倾斜树这些边界要手动验算
-
root == nullptr → 返回 0（不是 1）
- 单节点 → 列号只有 0 → 宽度 =
0 - 0 + 1 = 1
- 左斜树（只有 left 链）：n 层高 → 列号从 0 到 −(n−1) → 宽度 = n
- 同样长度的右斜树 → 列号从 0 到 +(n−1) → 宽度也是 n
- 实际调试时，建议手画 3 层满二叉树，标出各节点列号，确认
minCol = -2, maxCol = 2 → 宽度 = 5，再比对代码输出
root == nullptr → 返回 0（不是 1） 0 - 0 + 1 = 1 minCol = -2, maxCol = 2 → 宽度 = 5，再比对代码输出列号溢出一般不用担心理，在常规题目数据规模下 int 足够；但若树极度不平衡（千万级深度），列号可能超 int，这时得改用 long long 并检查输入约束。
