BFS without hashmap C++ Solution


  • 0
    T

    use two variables 'base' and 'off' to build the solution on the fly. See comments for more details.

        vector<vector<int>> verticalOrder(TreeNode* root) {
            vector<vector<int>> res;
            if (!root) return res;
            res.push_back(vector<int> ());
            //first : current node; second : off
            int base = 0, off, i, n, idx;
            deque<pair<TreeNode *, int>> dq(1, pair<TreeNode *, int> (root, 0));
            //BFS: from top to bottom
            while (!dq.empty()) {
                i = 0, n = dq.size();
                //process current level
                while (i < n) {
                    i++;
                    off = dq.front().second;
                    root = dq.front().first;
                    dq.pop_front();
                    //process current node
                    idx = base + off;
                    if (idx < 0) {
                        res.insert(res.begin(), vector<int> (1, root->val));
                        base++;//insertion before base will increase the base
                    }
                    else if (idx >= res.size()) {
                        res.push_back(vector<int> (1, root->val));
                    }
                    else {
                        res[idx].push_back(root->val);
                    }
                    //check next layer, from left to right
                    if (root->left)//turn left, decrease off
                        dq.push_back(pair<TreeNode *, int> (root->left, off - 1));
                    if (root->right)//turn right, increase off
                        dq.push_back(pair<TreeNode *, int> (root->right, off + 1));
                }
            }
            return res;
        }
    

Log in to reply
 

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