C++如何实现二叉树的垂直列序遍历输出 (按列扫描)-C++-PHP中文网

垂直列序遍历的核心是列号映射，必须同时记录节点的列号（col）和行号（row），用bfs实现并以map按列号升序存储，同列内按row升序排序，确保“从上到下、从左到右”输出。

c++如何实现二叉树的垂直列序遍历输出 (按列扫描)

垂直列序遍历的核心是列号映射，不是层序或中序

垂直列序遍历（Vertical Order Traversal）的本质是：同一列（column）的所有节点按**从上到下、从左到右**的顺序输出，列号以根为 0，左子节点列号减 1，右子节点加 1。它和层序遍历不同——不能只靠 queue 存节点；和中序也不同——列号不等于访问顺序。必须边遍历边记录每个节点的列号与行号（用于同列内排序），否则无法稳定输出。

常见错误是只用列号做 key，忽略行号，导致同列节点顺序错乱（比如父节点在子节点之后输出）；或者用 DFS 但没传行号，导致深度信息丢失。

必须携带两个坐标：col（列号）和 row（行号），根节点为 (0, 0)
推荐 BFS（层序）实现：天然保证同列内“上→下”，再按“左→右”补足（同一层中左子先入队，自然先出）
用 map<int vector int>>></int> 存：key 是列号，value 是 (row, val) 对，后续按 row 升序、再按入队顺序（即原树中从左到右）排序

用 BFS + map 实现列号分组与排序

BFS 遍历时对每个节点记录 (node, col, row) 元组，入队时更新子节点的 col 和 row。用 map 自动按键（列号）升序排列，避免手动排序列；每个列内暂存 (row, val)，最后对该列内所有元素按 row 排序（row 相同时，BFS 入队顺序已保证左子优先，无需额外判左右）。

示例关键片段：

map<int vector int>>> colMap;
queue<tuple int>> q; // node, col, row
q.push({root, 0, 0});
while (!q.empty()) {
    auto [node, col, row] = q.front(); q.pop();
    colMap[col].push_back({row, node->val});
    if (node->left)  q.push({node->left,  col - 1, row + 1});
    if (node->right) q.push({node->right, col + 1, row + 1});
}
// 输出：遍历 colMap，对每列内 vector 按 row 排序后取 val
</tuple></int>

为什么不用 unordered_map？列号顺序不能丢

unordered_map 不保证 key 的遍历顺序，而垂直遍历要求列号从小到大输出（如 -2, -1, 0, 1, 2）。若用 unordered_map，必须额外提取所有列号、排序后再遍历，多一次 O(k log k)（k 为列数）开销，且代码更啰嗦。直接用 map 更简洁安全——它底层是红黑树，插入和遍历都按 key 升序，零成本满足需求。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

列数通常远小于总节点数，map 的常数开销可接受
若极端追求性能（比如百万节点+稀疏列），可用 vector 手动维护 minCol/maxCol 范围，但绝大多数场景没必要
切勿用 unordered_map + 忘记排序列号，这是线上调试时最常卡住的点

同列内节点顺序：只比 row，不需额外判左右

同列内多个节点，只要它们的 row 不同，按 row 升序即可（上层优先）；如果 row 相同（即同一层、不同子树产生的同列节点，例如根的左孙子和右孙子落在同一列），此时 BFS 的入队顺序决定了它们在 vector 中的相对位置：左子树分支一定先于右子树分支被处理，因此左节点自然排在右节点前面。不需要在排序时额外比较节点在树中的左右位置。

排序写法示例（C++11+）：

for (auto& [col, nodes] : colMap) {
    sort(nodes.begin(), nodes.end()); // pair<int> 默认按 first(row) 升序，相等时按 second(val) 升序
    vector<int> colVals;
    for (auto& [r, v] : nodes) colVals.push_back(v);
    result.push_back(colVals);
}
</int></int>

注意：这里 sort 对 pair 的默认行为刚好符合要求，无需自定义 comparator；但如果节点值可能重复且你依赖原始左右顺序，就别用 pair 的 second 比较——不过题干只要求“从上到下、从左到右”，而 BFS 已确保这点。

真正容易漏的是：DFS 实现时忘记传 row，或把 row 错写成递归深度以外的值；BFS 实现时对子节点的 row + 1 写成 row 或 row++。这些 bug 导致同列节点顺序全乱，但错误现象又很隐蔽——输出看起来“差不多”，只是个别列颠倒。