BFS with deque, byebye to HashMap etc...

  • 0
    class Solution {
        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> ()); 
                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));
            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.