C++如何实现二叉树的垂序遍历（Vertical Order）-C++-PHP中文网

垂序遍历是按节点列坐标（x轴）分组，从左到右输出每列节点；同一列内先按行号自上而下排序，同行同列则按值升序排列；而层序遍历是按树的层级、从上到下从左到右依次访问节点，不依赖坐标，仅关注访问顺序。

c++如何实现二叉树的垂序遍历（vertical order）

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

垂序遍历不是按层、也不是按深度优先顺序，而是按节点在二维平面上的列坐标（x 轴）分组，从左到右输出每列内所有节点的值。同一列中，若多个节点行号（y 轴）不同，需按**自上而下**顺序排列；若行号相同（即同一层、同列），则按**节点值升序**排列（LeetCode 314 默认规则）。这和 BFS 或 DFS 的天然顺序都不一致，必须额外记录坐标信息。

用 map>> 存列→(行, 值) 是最稳妥的起点

直接用 map<int vector>></int> 会丢失行号，无法判断上下顺序；用 unordered_map 则列序不保，得额外排序。所以推荐：

map<int vector int>>> colMap; // key: 列号，value: {行号, 节点值}
</int>

插入时：根节点列号为 0，左子列号 -1，右子列号 +1；行号从 0 开始，每下一层 +1。BFS 和 DFS 都能实现，但 BFS 更自然——因为行号天然递增，插入时无需额外排序同一列内的元素。

colMap[col].emplace_back(row, node->val) 比 push_back({row, val}) 更高效
列号用 int 即可，极端情况（单边链表）最大深度约 1000，列范围不会溢出
不要用 multiset 或 priority_queue 替代 vector —— 同一列节点数少，排序开销小，且后续要统一按行号排序，vector + sort 更可控

遍历完后怎么正确排序每列内的节点

对每个 colMap[col]，需按「先行号升序，行号相同时值升序」排序：

C++ Code Review Master

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

下载

for (auto& [col, nodes] : colMap) {
    sort(nodes.begin(), nodes.end(), [](const auto& a, const auto& b) {
        return a.first != b.first ? a.first <p>注意：<code>a.first != b.first</code> 是关键判断，避免直接写 <code>a.first  导致错误排序（比如 (2,5) 和 (1,10) 会被错排）。</code></p>

如果题目不要求同列同行时排序值（如某些变体），去掉 a.second 即可
别漏掉 & 引用捕获，否则 sort 对副本操作，无效
返回结果时，每列提取 nodes[i].second 构成一个 vector<int></int>

BFS 实现比 DFS 更不容易错行号和列号

DFS 容易在递归调用中传错 row + 1 或 col - 1，尤其左右子树参数顺序颠倒；BFS 用队列显式维护 (node, row, col) 元组，逻辑清晰：

queue<tuple int>> q;
q.push({root, 0, 0});
while (!q.empty()) {
    auto [node, row, col] = q.front(); q.pop();
    colMap[col].emplace_back(row, node->val);
    if (node->left)  q.push({node->left,  row + 1, col - 1});
    if (node->right) q.push({node->right, row + 1, col + 1});
}
</tuple>

这里容易踩的坑：