987. Vertical Order Traversal of a Binary Tree

O(nlog(n/k)) time O(n) space
n是node数 k是column数 也是树的width
插入是O(n)
整理是O(k*(n/k)log(n/k)) = O(nlog(n/k))
跟314. Binary Tree Vertical Order Traversal的区别是要相同位置的数要按大小排序，所以排序优先级是左右上下大小，因此必须维护行号，理论上bfs和dfs均可，但dfs代码简单

/**
 * 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) {
        dfs(root, 0, 0);
        vector<vector<int>> res(mx - mn + 1);
        for (auto &&[i, v] : m) {
            sort(begin(v), end(v));
            for (const auto &[j, val] : v) {
                res[i - mn].push_back(val);
            }
        }
        return res;
    }

    void dfs(TreeNode *root, int i, int j) {
        if (!root) return;
        m[i].emplace_back(j, root->val);
        mn = min(mn, i);
        mx = max(mx, i);
        dfs(root->left, i - 1, j + 1); // 因为要保证自顶向下的顺序所以这里一定要+1不能-1
        dfs(root->right, i + 1, j + 1);
    }

    int mn = INT_MAX, mx = INT_MIN;
    unordered_map<int, vector<pair<int, int>>> m;
};

O(nlogn) time O(n) space
插入是O(nlogk) k是column数 也是树的width
整理是O(k*(n/k)log(n/k))
O(nlogk + k*(n/k)log(n/k)) = O(nlogk + nlog(n/k)) = O(nlog(k*(n/k))) = O(nlogn)

/**
 * 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) {
        dfs(root, 1000, 0); // 宽度从1000开始，层数从0开始
        vector<vector<int>> res;
        int prev = INT_MIN;
        for (auto &&p : m) {
            int curr = p.first / 1000; // 宽度即结果数组的row
            if (prev != curr) {
                res.push_back({});
                prev = curr;
            }
            res.back().insert(end(res.back()), begin(p.second), end(p.second));
        }
        return res;
    }

    void dfs(TreeNode *root, int i, int j) {
        if (!root) return;
        m[i * 1000 + j].insert(root->val);
        dfs(root->left, i - 1, j + 1); // 因为要保证自顶向下的顺序所以这里一定要+1不能-1
        dfs(root->right, i + 1, j + 1);
    }

    map<int, set<int>> m; // 同一坐标的数按数大小来排序所以要用set
};

如果没有1000这个限制条件，则把一维map转换成二维map

/**
 * 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) {
        dfs(root, 0, 0);
        vector<vector<int>> res;
        for (auto &&[k, s] : m) {
            res.push_back({}); // 对于同一列要按照从上到下的顺序输出，同一位置再按大小输出
            for (auto &&[_, v] : s) {
                res.back().insert(end(res.back()), begin(v), end(v));
            }
        }
        return res;
    }

    void dfs(TreeNode *root, int i, int j) {
        if (!root) return;
        m[i][j].insert(root->val);
        dfs(root->left, i - 1, j + 1); // 因为要保证自顶向下的顺序所以这里一定要+1不能-1
        dfs(root->right, i + 1, j + 1);
    }

    map<int, map<int, set<int>>> m;
};