LeetCode 987二叉树垂直遍历：节点重叠排序错误求助

问题分析 #

你当前代码用多维map（比如map<int, map<int, vector<int>>>）存储水平距离（x轴）、层级（y轴）对应的节点值，但同行同列（相同x和y）的节点值没有做升序排序，导致出现[1,6,5]这类错误输出，而正确应为[1,5,6]。

修改方案 #

核心是在收集完同一(x,y)下的所有节点值后，对该vector进行升序排序；或者在存储时就保证有序，但更高效的是在遍历到每个(x,y)对应的vector时，先排序再加入结果。

具体代码调整步骤 #

1. 保持原有的遍历逻辑（DFS或BFS都可以，这里以DFS为例），收集所有节点的(x, y, val)信息；
2. 用map<int, map<int, vector<int>>>存储时，同一(x,y)的val先存入vector；
3. 最终生成结果前，对每个map<int, vector<int>>里的每个vector执行升序排序；
4. 再按顺序把排序后的vector合并到结果中。

修正后的代码示例 #

#include <vector>
#include <map>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
private:
    void dfs(TreeNode* node, int x, int y, map<int, map<int, vector<int>>>& mp) {
        if (!node) return;
        mp[x][y].push_back(node->val);
        dfs(node->left, x-1, y+1, mp);
        dfs(node->right, x+1, y+1, mp);
    }
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<vector<int>> res;
        map<int, map<int, vector<int>>> mp; // x -> y -> list of values
        dfs(root, 0, 0, mp);
        
        for (auto& x_entry : mp) {
            vector<int> col;
            for (auto& y_entry : x_entry.second) {
                // 对同一y层级的节点值进行升序排序
                sort(y_entry.second.begin(), y_entry.second.end());
                // 将排序后的元素加入当前列
                col.insert(col.end(), y_entry.second.begin(), y_entry.second.end());
            }
            res.push_back(col);
        }
        return res;
    }
};

关键说明 #

• 这里的y表示层级（从上到下递增，根节点为0），map的key天然有序，保证同列节点按从上到下的顺序遍历；
• 对每个y对应的vector排序，直接解决了同行同列节点值的升序要求；
• 如果用BFS遍历，逻辑类似，只需在记录每个节点的x和y后存入对应map，最后对每个y层的vector执行排序即可。

内容的提问来源于stack exchange，提问作者Ravi Kumar