987.vertical-order-traversal-of-

关键词和模型构建

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        if(!root) return {};
        int min_x = INT_MAX;
        int max_x = INT_MIN;
        map<pair<int,int>,set<int>> h;  //{y,x} ->{vals}
        traverse(root,0,0,min_x,max_x,h);
        vector<vector<int>> ans(max_x - min_x + 1);
        for(const auto& m:h){
            int x = m.first.second - min_x;
            ans[x].insert(end(ans[x]), begin(m.second), end(m.second));
        }
        return ans;
    }

    void traverse(TreeNode* root, int x, int y, int& min_x, int& max_x,
                                map<pair<int,int>, set<int>>& h ){
            if(!root) return;
            min_x = min(min_x, x);
            max_x = max(max_x, x);
            h[{y,x}].insert(root->val);
            traverse(root->left, x-1, y+1, min_x, max_x,h);
            traverse(root->right,x+1, y+1, min_x,max_x,h);
    }
};