BFS with deque, byebye to HashMap etc...


  • 0
    W
    class Solution {
    public:
        vector<vector<int>> verticalOrder(TreeNode* root) {
            if (!root)
                return vector<vector<int>>();
    
            deque<vector<int>> buckets;
            int left=0; // how many vectors have been pushed_front to deque
    
            vector<pair<TreeNode*, int>> bfs;
            bfs.push_back(std::make_pair(root, 0));
            
            int i=0;
            while (i != bfs.size()) {
                if (bfs[i].second<0 && abs(bfs[i].second)>left)
                {
                    // need to expand to front
                    buckets.push_front(vector<int> ()); 
                    left++;
                }
                
                if (left + bfs[i].second >= buckets.size())
                    buckets.push_back(vector<int> ()); // expend to back
                
                buckets[left + bfs[i].second].push_back(bfs[i].first->val);
                    
                if (bfs[i].first->left) 
                    bfs.push_back(make_pair(bfs[i].first->left, bfs[i].second-1));
                if (bfs[i].first->right)
                    bfs.push_back(make_pair(bfs[i].first->right, bfs[i].second+1));
                i++;
            }
            
            return vector<vector<int>> (buckets.begin(), buckets.end());
        }
    };

Log in to reply
 

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