Java simple and easy understand solution based on naive BST


  • 0
    Q

    use only BST. the key point is to merge the interval like [1,1] [3,3] if 2 was added. My solution is to find the rightmost or the leftmost in the sub tree to merge.

     class Tree {
     Interval interval;
     Tree left;
     Tree right;
     
     Tree(int num) {interval = new Interval(num,num);}
     }
    
    public class SummaryRanges {
    
    /** Initialize your data structure here. */
    Tree root;
    public SummaryRanges() {
        
    }
    
    public void addNum(int val) {
        if(root == null) root = new Tree(val);
        else add(root,val);
    }
    
    public void add(Tree now,int val){
        if(now.interval.start <= val && val <= now.interval.end) return;
        else if(now.interval.start == val+1){
            now.interval.start = val;
            Tree parent = now;
            Tree find = now.left;
            while(find != null && find.right != null) {parent = find;find = find.right;}
            if(find != null && (find.interval.end == now.interval.start || find.interval.end+1 == now.interval.start)){
                now.interval.start = find.interval.start;
                if(parent == now) parent.left = find.left;
                else parent.right = find.left;
            }
        }
        else if(now.interval.end + 1 == val){
            now.interval.end = val;
            Tree parent = now;
            Tree find = now.right;
            while(find != null && find.left != null){parent = find;find = find.left;}
            if(find != null &&  (find.interval.start == now.interval.end || find.interval.start-1 == now.interval.end)){
                now.interval.end = find.interval.end;
                if(parent == now) parent.right = find.right;
                else parent.left = find.right;
            }
        }
        else if(now.interval.start > val){
            if(now.left == null) now.left = new Tree(val);
            else add(now.left,val);
        }
        else{
            if(now.right == null) now.right = new Tree(val);
            else add(now.right,val);
        }
    }
    
    public List<Interval> getIntervals() {
        List ret = new ArrayList();
        inOrder(root,ret);
        return ret;
    }
    
    public void inOrder(Tree now, List ret){
        if(now != null){
            inOrder(now.left,ret);
            ret.add(now.interval);
            inOrder(now.right,ret);
        }
    }
    

    }


Log in to reply
 

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