987. Vertical Order Traversal of a Binary Tree

https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/

以root为(0, 0)，按x轴从小到大输出所有结点，相同x值的放在一个vector里，且按y轴从小到大排序，其中相同(x, y)的再按值大小排序。BFS或DFS从root遍历并记录下对应的坐标，对每个坐标再维护一个treeset按序记录相同坐标下的结点值。

/*
 * @lc app=leetcode id=987 lang=cpp
 *
 * [987] Vertical Order Traversal of a Binary Tree
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        unordered_map<int, unordered_map<int, set<int>>> m;
        queue<pair<int, TreeNode*>> q;
        q.push({0, root});
        int mi = 0, y = 0;
        while (!q.empty()) {
            for (int i = q.size() - 1; i >= 0; --i) {
                const auto &t = q.front();
                const auto cur = t.second;
                m[t.first][y].insert(cur->val);
                if (cur->left != nullptr) q.push({t.first - 1, cur->left});
                if (cur->right != nullptr) q.push({t.first + 1, cur->right});
                mi = min(mi, t.first);
                q.pop(); 
            }
            ++y;
        }
        vector<vector<int>> res(m.size());
        for (int i = 0, j = mi; i < m.size(); ++i, ++j) {
            for (int k = 0; k < y; ++k) {
                if (!m[j].count(k)) continue;
                for (const auto e : m[j][k]) res[i].push_back(e);
            }
        }
        return res;
    }
};
// @lc code=end