打卡

[Yukibei]

class Solution {
public:
vector<vector> verticalTraversal(TreeNode root) {
vector<tuple<int, int, int>> data;
function<void(TreeNode, int, int)> dfs = [&](TreeNode *node, int row, int col) {
if (node == nullptr) {
return;
}
data.emplace_back(col, row, node->val);
dfs(node->left, row + 1, col - 1);
dfs(node->right, row + 1, col + 1);
};
dfs(root, 0, 0);

    vector<vector<int>> ans;
    ranges::sort(data);
    int last_col = INT_MIN;
    for (auto &[col, _, val]: data) {
        if (col != last_col) {
            last_col = col;
            ans.push_back({});
        }
        ans.back().push_back(val);
    }
    return ans;
}

};

。
时间复杂度：O(nlogn)，其中 nnn 为二叉树的节点个数。瓶颈在排序上。
空间复杂度：O(n)。