Share my C++ solution using BFS and Hash Map


  • 0
    M
    vector<vector<int>> verticalOrder(TreeNode* root) {
            vector<vector<int>> ret;
            if (!root) return ret;
            unordered_map<int, vector<int>> M;
            queue<pair<TreeNode*, int>> Q;
            Q.push({root, 0});
            int Max = 0, Min = 0;
            while (!Q.empty()) {
                pair<TreeNode*, int> p = Q.front();
                Q.pop();
                Max = max(Max, p.second);
                Min = min(Min, p.second);
                M[p.second].push_back(p.first->val);
                if (p.first->left) Q.push({p.first->left, p.second+1});
                if (p.first->right) Q.push({p.first->right, p.second-1});
            }
            for (int i = Max; i >= Min; --i) {
                ret.push_back(M[i]);
            }
            return ret;
        }
    

Log in to reply
 

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