3ms BFS C++ Short Solution


  • 0
    F
    /**
     * 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 == nullptr) return vector<vector<int>>();
            // Map between each column level and the nodes in that column.
            map<int, vector<int>> t;
            // A queue of nodes and their column level.
            queue<pair<TreeNode*, int>> q;
            
            q.push({ root, 0 });
            while (!q.empty()) {
                auto n = q.front();
                q.pop();
                // Visit current node n.first and put it in its column.
                t[n.second].push_back(n.first->val);
    
                if (n.first->left != nullptr)
                    q.push({ n.first->left, n.second - 1 });
                
                if (n.first->right != nullptr)
                    q.push({ n.first->right, n.second + 1 });
            }
            
            // Traverse the map based on the column level in ascending order
            // and put them in the solution in that same order.
            vector<vector<int>> sln;
            for (auto& c : t) {
                sln.push_back(c.second);
            }
            return sln;
        }
    };
    

  • 0
    Y

    Why map instead of unordered_map is used?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.