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

垂直列序遍历是按列坐标（根为0，左减1、右加1）分组，每列内按行号升序（从上到下）、同行列号相同时保持左→右顺序；而层序遍历是按深度逐层、从左到右访问节点。

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

什么是垂直列序遍历，和层序遍历有什么区别？

垂直列序遍历（Vertical Order Traversal）不是按层、也不是按深度优先顺序，而是按节点在二维空间中的「列坐标」分组输出：根节点列号为 0，左子节点列号减 1，右子节点列号加 1。同一列的所有节点，按从上到下、从左到右的顺序输出（注意：不是按层序简单拼接，而是需保证上层节点一定排在下层前面；若同层同列，左子树节点先于右子树）。

常见错误是直接用 DFS 记录列号后按列排序——这会丢失“上下优先级”，导致同列中下层节点排到上层前面。必须保留行号（或深度）信息，用于同列内二次排序。

用 map>> 存列→(行号, 值) 是最稳妥的结构

map 自动按键（列号）升序排列，vector 存该列所有 (row, value) 对，后续对每个 vector 按 row 升序、再按插入顺序（即左→右）稳定排序即可。

DFS 过程中传入当前 col 和 row，递归左右子树时分别传 col-1 / col+1、row+1
不要用 unordered_map：列号需从小到大输出，否则得额外收集 key 再排序，徒增复杂度
注意：同列同层节点的相对顺序依赖 DFS 的访问顺序（先左后右），只要 DFS 严格按 left → root → right 或 root → left → right（推荐后者），就能保证左子树节点先被 push_back

// 示例片段（假设 TreeNode 定义含 val, left, right）
void dfs(TreeNode* node, int col, int row, map<int vector int>>& cols) {
    if (!node) return;
    cols[col].emplace_back(row, node->val);
    dfs(node->left,  col - 1, row + 1, cols);
    dfs(node->right, col + 1, row + 1, cols);
}
</int>

输出前必须对每列 vector 按 (row, 插入序) 排序

cols[col] 中的元素顺序只反映 DFS 访问顺序，不保证行号递增。必须显式排序：

C++ Code Review Master

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

下载

排序规则：先按 first（即 row）升序；若 row 相同，保持原有相对顺序（stable_sort 或自定义比较时不破坏等价元素顺序）
错误做法：用 sort(cols[col].begin(), cols[col].end()) —— 默认按 pair 的字典序，虽通常可行，但隐含依赖，不如显式写清楚

for (auto& [col, vec] : cols) {
    stable_sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) {
        return a.first <h3>BFS 实现更直观，但需额外存列号和行号</h3><p>DFS 容易写错行号传递逻辑，BFS 更符合“从上到下”的直觉：</p>