垂直列序遍历的核心是列号映射：以根为0，左减1、右加1；必须用BFS保证同列内top-to-bottom顺序，且用map（而非unordered_map）天然按列号升序输出。
垂直列序遍历的核心是列号映射，不是层序或中序
垂直列序遍历（Vertical Order Traversal）的关键在于：**同一列的所有节点（无论深度）必须归为一组，且列号由根节点为 0、左子节点减 1、右子节点加 1 决定**。它和层序遍历不同——不能只靠 queue 记录节点；和中序也不同——顺序不由访问时机决定，而由列位置决定。实际中容易误以为“DFS 中序走一遍就能按列收集”，结果发现同一列内节点顺序错乱（比如上层节点排在下层之后），因为 DFS 不保证列内按 top-to-bottom 排序。
正确做法是：**BFS + 列号记录 + 按列号分组 + 同列内保持插入顺序（即自然的 BFS 深度顺序）**。这样能天然保证同一列中，上层节点先于下层节点被加入。
- 用
queue存储pair<treenode int></treenode>，第二个值是当前节点列号 - 用
map<int vector>></int>收集：key 是列号（自动升序），value 是该列所有节点值（按 BFS 遍历顺序） - 根节点入队时列号为
0；左子节点列号 = 父列号 -1；右子节点列号 = 父列号 +1
为什么必须用 map 而不是 unordered_map
输出要求是“从左到右”按列扫描，也就是列号从小到大。如果用 unordered_map，遍历 key 时顺序不可控，必须额外排序 key，反而增加复杂度。而 map<int ...></int> 的 key 天然有序（红黑树实现），迭代时就是 col -2 → -1 → 0 → 1 → 2 的顺序，直接 for 循环即可输出。
注意：C++17 起 std::map 迭代器保证升序；若用 std::unordered_map，哪怕手动 vector 提取 key 再 sort，也会多一次 O(K log K) 开销（K 是列数），不必要。
立即学习“C++免费学习笔记（深入）”；
-
map插入均摊 O(log N)，总时间 O(N log N)，可接受 - 若真要 O(N) 时间，可用
unordered_map+ 两个变量记录 min_col/max_col，在 BFS 过程中动态更新，最后从 min_col 遍历到 max_col ——但代码变长，易错 - 新手建议无脑用
map，逻辑清晰不易漏
BFS 实现中容易漏掉的边界检查
常见错误是只检查 node != nullptr，却忘了对左右子节点做空指针判断再入队。一旦某个节点的 left 或 right 是 nullptr，还强行访问其成员或计算列号，就会崩溃。
标准写法必须显式判空：
if (node->left) {
q.push({node->left, col - 1});
}
if (node->right) {
q.push({node->right, col + 1});
}
- 漏掉
if直接q.push({node->left, ...})是段错误高发点 - 列号计算必须和子节点绑定，不能“先 push 再算”，否则会把
nullptr的列号也塞进去 - 如果题目要求同一列内“深度相同时按节点值升序”，才需要额外用
priority_queue或vector+sort；但基础垂直遍历只要求 top-to-bottom，BFS 天然满足，无需排序
完整可跑的最小实现（含测试结构）
下面是一个去掉冗余、能直接编译运行的版本，重点看数据流动逻辑：
vector<vector<int>> verticalOrder(TreeNode* root) {
if (!root) return {};
map<int, vector<int>> cols;
queue<pair<TreeNode*, int>> q;
q.push({root, 0});
while (!q.empty()) {
auto [node, col] = q.front(); q.pop();
cols[col].push_back(node->val);
if (node->left) q.push({node->left, col - 1});
if (node->right) q.push({node->right, col + 1});
}
vector<vector<int>> res;
for (auto& p : cols) res.push_back(p.second);
return res;
}
这个函数返回的是 vector<vector<int>>，每项对应一列（从最左列到最右列），每列内元素顺序即 BFS 访问顺序。真正难的不是写代码，而是理解“列号必须随节点传播”和“map 的有序性不可替代”——这两点一旦想岔，调试半天也调不对。
