Simple and 3 ms C++ BFS Algorithm


  • 0
    Y

    The idea is to use a index to mark the index of the vector in the result vector. The left child will have current index - 1 and right child will have a current index + 1.
    The offset will deal with minus index to scale it to real index.

    class Solution {
    public:
        vector<vector<int>> verticalOrder(TreeNode* root) {
            if (!root) return res;
            que.push({root, 0});
            while (!que.empty()) {
                pair<TreeNode*, int> p = que.front();
                que.pop();
                if (p.second < 0 && p.second + offset < 0) {
                    res.insert(res.begin(), {p.first->val});
                    offset++;
                }
                else if (p.second + offset >= res.size())
                    res.push_back({p.first->val});
                else
                    res[p.second + offset].push_back(p.first->val);
                if (p.first->left) que.push({p.first->left, p.second - 1});
                if (p.first->right) que.push({p.first->right, p.second + 1});
            }
            return res;
        }
        
    private:
        vector<vector<int> > res;
        queue<pair<TreeNode*, int> > que;
        int offset = 0;
    };
    

Log in to reply
 

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