987. Vertical Order Traversal of a Binary Tree

[jason89521]

Practice Dates

• 2024/05/20

Description

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

Solution

The valMap's key is [row, col], and its value is a multiset of the node's values where the node is in [row, col]. We use a multiset because it sorts the elements automatically.

The queue q contains the node and its column.

We use BFS to traverse the tree level by level. When visiting a node, we insert the value with its row and column into the valMap.

Finally, we update the result using the valMap.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        map<pair<int, int>, multiset<int>> valMap;
        queue<pair<TreeNode*, int>> q;
        q.emplace(root, 0);
        int row = -1, minCol = 0, maxCol = 0;
        while (!q.empty()) {
            row++;
            auto qSize = q.size();
            for (int i = 0; i < qSize; i++) {
                auto myPair = q.front();
                q.pop();
                auto node = myPair.first;
                auto col = myPair.second;
                if (node->left) {
                    q.emplace(node->left, col-1);
                }
                if (node->right) {
                    q.emplace(node->right, col+1);
                }

                valMap[{row, col}].insert(node->val);
                minCol = min(minCol, col);
                maxCol = max(maxCol, col);
            }
        }

        vector<vector<int>> result(maxCol - minCol + 1);
        for (auto it = valMap.begin(); it != valMap.end(); it++) {
            auto idx = it->first.second - minCol;
            auto nodeVals = it->second;
            result[idx].insert(result[idx].end(), nodeVals.begin(), nodeVals.end());
        }

        return result;
    }
};

Performance

Time complexity: