C++ descriptive solution with zero bugs


  • 0
    G
    class Solution {
        struct QueueNode {
            TreeNode* node;
            int column;
            QueueNode(TreeNode* n, int c) : node(n), column(c) {}
        };
        queue<QueueNode> q;     // queue to implement BFS
    
        map<int, vector<int>> res_map;
        void add_to_res_map(int val, int c) {
            if (res_map.count(c) == 0) {
                // add an empty vector if we are populating 'c' column's vector first element
                pair<int, vector<int> > p(c, vector<int>());
                res_map.insert(p);
            }
            res_map.at(c).push_back(val);
        }
        
    public:
        vector<vector<int>> verticalOrder(TreeNode* root) {
            // Implement BFS. Additionally put a tag for every element denoting its column
            // Keep an ordered map which holds {column -> elements belonging to that column} mapping
            vector<vector<int> > res;
            if (root != NULL) {
                q.push(QueueNode(root, 0));
            }
            while (q.empty() == false) {
                int c = q.front().column;
                TreeNode* node = q.front().node;
                q.pop();
                add_to_res_map(node->val, c);
                if (node->left != NULL) {
                    q.push(QueueNode(node->left, c - 1));
                }
                if (node->right != NULL) {
                    q.push(QueueNode(node->right, c + 1));
                }
            }
            
            // convert map to vector
            for (map<int, vector<int> >::iterator i = res_map.begin(); i != res_map.end(); i++) {
                res.push_back(i->second);
            }
            return res;
        }
    };
    

Log in to reply
 

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