I am working on the LeetCode problem 987: Vertical Order Traversal of a Binary Tree:

Given the root of a binary tree, calculate the vertical order traversal of the binary tree.

For each node at position (row, col), its left and right children will be at positions (row 1, col - 1) and (row 1, col 1) respectively. The root of the tree is at (0, 0).

The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

Return the vertical order traversal of the binary tree.

This is my code:

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) 
    {
        map<int, map<int, vector<int> > > nodes; // actual mapping
        queue<pair<TreeNode*, pair<int, int> > > q; // for storing in queue along with HD and level no.
        vector<vector<int>> ans;
        vector<int> cur_vec;
        
        if(!root){
            return ans;
        }
        
        q.push(make_pair(root, make_pair(0, 0)));
        
        while(!q.empty()){
            pair<TreeNode*, pair<int, int> > temp = q.front(); // for storing the queue.front value in temp
            q.pop();
            TreeNode* frontNode = temp.first;
            int hd = temp.second.first;
            int level = temp.second.second;
            
            nodes[hd][level].push_back(frontNode->val);
            
            if(frontNode->left)
                q.push(make_pair(frontNode->left, make_pair(hd-1, level 1)));
            if(frontNode->right)
                q.push(make_pair(frontNode->right, make_pair(hd 1, level 1)));
        }
        for(auto i: nodes){
            for(auto j: i.second){
                for(auto k: j.second){
                    cur_vec.push_back(k);
                } 
            }             
            ans.push_back(cur_vec);
            cur_vec.resize(0);
        }     
        return ans;          
    }
}; 

I've used a multidimensional map in my answer which maps horizontal distance to levels. It works for several test cases, but it fails to pass the test case when two nodes overlap each other and the smaller one has to come first.

For instance, here the correct output for one vertical line is [1,5,6] but mine is [1,6,5] (the overlapping nodes are 6 and 5):

What should I change to make it work?

CodePudding user response：

In your final loop, you can just add a call to sort on the inner vector (that corresponds to a certain horizontal distance and certain level). It is in that vector you could get overlapping nodes.

So:

        for(auto i: nodes){
            for(auto j: i.second){
                sort(j.second.begin(), j.second.end());  // <-- added
                for(auto k: j.second){
                    cur_vec.push_back(k);
                } 
            }             
            ans.push_back(cur_vec);
            cur_vec.resize(0);
        }