314. Binary Tree Vertical Order Traversal

bfs O(n) time 给每个node一个伪下标并维护最小最大下标，最后利用最小下标来还原真实下标
必须自顶向下自左向右 dfs如果不维护行号会违反 bfs完美符合不用维护行号只需要把每个数放到对应column即可所以选择bfs 即排序优先级是左右上下

/**
 * 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>> verticalOrder(TreeNode* root) {
        if (!root) return {};
        vector<pair<int, TreeNode *>> v;
        queue<pair<int, TreeNode *>> q;
        q.emplace(0, root);
        int mn = INT_MAX, mx = INT_MIN;
        while (!q.empty()) {
            auto [idx, x] = q.front(); q.pop();
            v.emplace_back(idx, x);
            mn = min(mn, idx);
            mx = max(mx, idx);
            if (x->left) {
                q.emplace(idx - 1, x->left);
            }
            if (x->right) {
                q.emplace(idx + 1, x->right);
            }
        }
        vector<vector<int>> res(mx - mn + 1); // 利用最大最小下标提前分配内存
        for (auto [idx, x] : v) {
            res[idx - mn].push_back(x->val);
        }
        return res;
    }
};

/**
 * 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>> verticalOrder(TreeNode* root) {
        if (!root) return {};
        unordered_map<int, vector<TreeNode *>> m;
        queue<pair<int, TreeNode *>> q;
        q.emplace(0, root);
        int mn = INT_MAX, mx = INT_MIN;
        while (!q.empty()) {
            auto p = q.front(); q.pop();
            int idx = p.first;
            auto x = p.second;
            m[idx].push_back(x);
            mn = min(mn, idx);
            mx = max(mx, idx);
            if (x->left) {
                q.emplace(idx - 1, x->left);
            }
            if (x->right) {
                q.emplace(idx + 1, x->right);
            }
        }
        vector<vector<int>> res(mx - mn + 1);
        for (int i = mn; i <= mx; ++i) {
            for (auto x : m[i]) {
                res[i - mn].push_back(x->val);
            }
        }
        return res;
    }
};