clean, concise C++11 BFS + map solution.


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

  • 0
    Y

    Why map is used instead of unordered_map? I will consider map have better search efficiency. Meanwhile we can keep a min_index, and start from min_index search in the hashmap..


  • 0
    W

    @ydxu16 unordered_map is ok too, is on average faster than map, but map is good enough in this case too.


Log in to reply
 

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