C++, 8ms without using HashMap


  • 5
    X

    Well, we are using hashmap because we want the container to be two-way-expandable.

    Thus, we can use other data structures like double linked list to contain these TreeNode values.

    However, I want to introduce a "traditional" method using vector.

    Basically, it's like using two vectors to expand into two directions, left and right. And at the end, just combine these two vector toghther.

    Well, I have to admit that this method is not so serious... The most elegant way is using hashmap, though.

    - Without using hashmap:

    class Solution {
    public:
        vector<vector<int>> verticalOrder(TreeNode* root) {
            std::queue<pair<int, TreeNode*>> q;
            vector<vector<int>> left;
            vector<vector<int>> right;
            vector<int> mid;
            if(!root) return left;
            q.push({0,root});
            while(!q.empty()){
                auto p = q.front();
                q.pop();
                if(p.first == 0) mid.push_back(p.second->val);
                else if(p.first > 0){
                    if(p.first > right.size()) right.push_back(vector<int>());
                    right[p.first-1].push_back(p.second->val);
                }
                else{
                    if(0-p.first > left.size()) left.push_back(vector<int>());
                    left[-1-p.first].push_back(p.second->val);
                }
                if(p.second->left) q.push({p.first-1, p.second->left});
                if(p.second->right) q.push({p.first+1, p.second->right});
            }
            int  r = right.size();
            reverse(left.begin(), left.end());
            left.push_back(mid);
            for(int i=0; i<r; i++) left.push_back(right[i]);
            return left;
        }
    };
    

    - Using hashmap:

    class Solution {
    public:
        vector<vector<int>> verticalOrder(TreeNode* root) {
            std::map<int, vector<int>> mp;
            std::queue<pair<int, TreeNode*>> q;
            vector<vector<int>> ret;
            if(root) q.push({0, root});
            while(!q.empty()){
                auto p = q.front();
                q.pop();
                mp[p.first].push_back(p.second->val);
                if(p.second->left) q.push({p.first-1, p.second->left});
                if(p.second->right) q.push({p.first+1, p.second->right});
            }
            for(auto it=mp.begin(); it!=mp.end(); ++it)
                ret.push_back(it->second);
            return ret;
        }
    };

  • 4
    Q

    Hi @ xuweineo2, in your second solution, what you've used is a tree map, not a hash map.

    C++ std::map is tree map, unordered_map is hash map. In fact, hash map wouldn't work because the order is not kept in the end.


Log in to reply
 

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