c++ BFS queue and unordered_map solution, by Chaoyang He


  • 0
        vector<vector<int>> verticalOrder(TreeNode* root) {
            vector<vector<int> > result;
            unordered_map<int, vector<int> > verticalMap;
            if(root == NULL){
                return result;
            }
            queue<pair<TreeNode*, int> > q;
            q.push(make_pair(root,0));
            int minCol = 0;
            int maxCol = 0;
            while(!q.empty()){
                TreeNode* node = q.front().first;
                int column = q.front().second;
                verticalMap[column].push_back(node->val);
                q.pop();
                
                if(node->left != NULL){
                    q.push(make_pair(node->left, column-1));
                    minCol = min(minCol, column-1);
                }
                if(node->right != NULL){
                    q.push(make_pair(node->right, column+1));
                    maxCol = max(maxCol, column+1);
                }
            }
            for(int i = minCol; i <= maxCol; i++){
                result.push_back(verticalMap[i]);
            }
            return result;
        }
    

Log in to reply
 

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