Why? C++ Using segment tree and runs good but got Output Limit Exceed!?


  • 0
    M

    Hey guys, have you met the same problem? I'm using segment tree to implement and I got the exactly same answer as expected when the test case was adding number from 1 to 2000. But I always get OLE error, can anyone tell me why this is happening?

    class SummaryRanges {
    public:
    
    struct segTreeNode{
        Interval in;
        segTreeNode *left;
        segTreeNode *right;
        segTreeNode (int s,int l):in(s,l),left(nullptr),right(nullptr){}
    };
    
    /** Initialize your data structure here. */
    segTreeNode* rt;
    
    SummaryRanges() {
        rt=nullptr;
    }
    
    void addNum(int val) {
        addNum(val,rt);
    }
    
    void addNum(int val, segTreeNode *&root){
        if(!root){
            root=new segTreeNode(val,val);
            return;
        }
        if(val>=(root->in).start&&val<=(root->in).end)return;
        if(val==(root->in).start-1){
            (root->in).start=val;
            if(root->left&&(root->left->in).end==val-1){
                (root->in).start=(root->left->in).start;
                root->left=root->left->left;
            }
            return;
        }else if(val==(root->in).end+1){
            (root->in).end=val;
            if(root->right&&(root->right->in).start==val+1){
                (root->in).end=(root->right->in).end;
                root->right=root->right->right;
            }
            return;
        }else if(val<(root->in).start)addNum(val, root->left);
        else addNum(val,root->right);
        
    }
    
    vector<Interval> getIntervals() {
        return getIntervals(rt);
    }
    
    vector<Interval> getIntervals(segTreeNode* root){
        vector<Interval>res;
        if(!root)return res;
        
        vector<Interval>le=getIntervals(root->left),ri=getIntervals(root->right);
        le.push_back(root->in);
        if(!ri.empty())le.insert(le.end(),ri.begin(),ri.end());
        return le;
    }
    

    };


  • 1
    S

    I think the following example could show the problem. Insert numbers as follows:

    5, 1, 3, 4

    This will create the following tree:

    after inserting 5:  root = 5, no children
    after inserting 1:  root = 5, left child = 1
    after inserting 3:  root = 5, left child = 1, left-right child = 3
    after inserting 4:  root = 4-5, left child = 1, left-right child = 3
    

    This leaves you with one interval too many, I believe.


Log in to reply
 

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