[C++] Why using multiset to represent <depth, value> got Wrong Answer?


  • 0
    N

    I am using multiset here, the element inside the multiset is pair<int,int> whose first means the depth, whose second means the value. But why it always got WA?

    class Solution {
    public:
        
        void preorder(TreeNode* root, map<int, multiset<pair<int,int>>> &m, int index, int depth) {
            if(!root)
                return;
            m[index].insert({depth,root->val});
            preorder(root->left, m, index-1, depth+1);
            preorder(root->right, m, index+1, depth+1);
        }
    
        vector<vector<int>> verticalOrder(TreeNode* root) {
            map<int,multiset<pair<int,int>>> m; // BST
            vector<vector<int>> res;
            preorder(root,m,0,0);
            for(const pair<int, multiset<pair<int,int>>> &p: m) {
                vector<int> col;
                for(const pair<int,int> &k : p.second)
                    col.push_back(k.second);
                res.push_back(col);
            }
            return res;
        }
    };
    

  • 0
    N

    I think I found the reason: because for overlapping points, the judge is doing exact order match. The algorithm itself has no problem I believe.


Log in to reply
 

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