2 C++ Solution with hashmap and 2 vectors respectively


  • 0
    H

    C++ people please do realize that maps are implemented as binary search trees (Red-Black Tree) while unordered_maps are implemented as hash table. This library implementation detail would cause significant difference in running time, since we all know that search, removal, and insertion operations on BST have logarithmic complexity while those operations on hash table have average constant-time complexity.

    public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        if (!root) return vector<vector<int>> ();
        /**
         * sol1: using level-traversal with two vectors storing elements which their column is less 
         * than and equal to/greater than root, respectively.
         * By using level-traversal, it can promise the order in each column is from top to bottom
         * 
         * Time O(N), Space O(N).
         **/ 
        vector<vector<int>> pos; // store those elements which their column are as root or on the right of root
        vector<vector<int>> neg; // store those elements which their column are on the left of root
        queue<pair<TreeNode*, int>> nodeQ;
        nodeQ.push(make_pair(root, 0));
        while (!nodeQ.empty()) {
            pair<TreeNode*, int> node = nodeQ.front();
            nodeQ.pop();
            pushToVec(pos, neg, node.first, node.second);
            if (node.first->left)
                nodeQ.push(make_pair(node.first->left, node.second-1));
            if (node.first->right)
                nodeQ.push(make_pair(node.first->right, node.second+1));
        }
        reverse(neg.begin(), neg.end());
        neg.insert(neg.end(), pos.begin(), pos.end()); 
        return neg;
        
        /**
         * sol2: using level-traversal with hash table 
         * Time O(N), Space O(N)
         **/ 
        vector<vector<int>> res;
        int minCol = INT_MAX, maxCol = INT_MIN;
        unordered_map<int, vector<int>> cols;
        queue<pair<TreeNode*, int>> nodeQ;
        nodeQ.push(make_pair(root, 0));
        while (!nodeQ.empty()) {
            pair<TreeNode*, int> node = nodeQ.front();
            nodeQ.pop();
            cols[node.second].push_back(node.first->val);
            minCol = min(minCol, node.second);
            maxCol = max(maxCol, node.second);
            if (node.first->left)
                nodeQ.push(make_pair(node.first->left, node.second-1));
            if (node.first->right)
                nodeQ.push(make_pair(node.first->right, node.second+1));
        }
        
        for (int i=minCol; i<=maxCol; i++) 
            res.push_back(cols[i]);
        
        return res;
    }
    
    private:
    void pushToVec(vector<vector<int>>& pos, vector<vector<int>>& neg, TreeNode* root, int curRange) {
        if (curRange>=0) {
            if (pos.size()<curRange+1)
                pos.push_back(vector<int>());
            pos[curRange].push_back(root->val);
        } else {
            if (neg.size()<-curRange)
                neg.push_back(vector<int>());
            neg[-curRange-1].push_back(root->val);
        }       
    }

Log in to reply
 

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