C++, 8ms, using BFS and Hashmap


  • 0
    W
    class Solution {
    public:
        vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> res;
        map<int,vector<int>> hashmap;
        queue<pair<int,TreeNode*>> q;
        if(root)
            q.push(make_pair(0,root));
        while(!q.empty())
        {
            pair<int,TreeNode*> cur=q.front();
            q.pop();
            hashmap[cur.first].push_back(cur.second->val);
            if(cur.second->left)
                q.emplace(cur.first-1,cur.second->left);
            if(cur.second->right)
                q.emplace(cur.first+1,cur.second->right);
        }
        for(auto i:hashmap)
            res.push_back(i.second);
        return res;
        }
    };

  • 0

    What's the point of the inner loop? You can just remove it and the solution still works.

    You could also use q.push({...}) or q.emplace(...) instead of q.push(make_pair(...)).


  • 0
    W

    Yes, BFS in this problem doesn't need a inner loop. Thank you for your suggestion, I have updated my post :-)


Log in to reply
 

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