BST rebalance strategy not implmented 220ms


  • 0
    L
    /**
     * Definition for an interval.
     * public class Interval {
     *     int start;
     *     int end;
     *     Interval() { start = 0; end = 0; }
     *     Interval(int s, int e) { start = s; end = e; }
     * }
     */
    public class SummaryRanges {
        class TreeNode{
            Interval interval;
            TreeNode left;
            TreeNode right;
            TreeNode parent;
            int count;
            public TreeNode(int count, Interval interval){
                this.interval = interval;
                this.count = count;
            }
            public TreeNode findLeft(){
                if (this.left == null){
                    
                    if (this.parent!=null&&this.parent.right == this){
                        return this.parent;
                    }else return null;
                }else{
                    TreeNode curr = this.left;
                    while(curr.right!=null){
    
                        curr=curr.right;
                    }
                    return curr;
                }
                
            }
            public TreeNode findRight(){
    
                if (this.right == null){
                    
                    if (this.parent!=null&&this.parent.left == this){
                        return this.parent;
                    }else return null;
                }else{
                    TreeNode curr = this.right;
                    while(curr.left!=null){
    
                        curr=curr.left;
                    }
                    return curr;
                }
                
            }
            public void decrementPathCount(TreeNode start){
                while(start.parent!=null){
                    
                    start.parent.count--;
                    start=start.parent;
                }
            }
            public void mergeLeft(TreeNode left, TreeNode curr){
                if (left == null) return;
                if (curr.interval.start-1<=left.interval.end){
                    curr.interval.start = left.interval.start;
                    decrementPathCount(left);
                    if(curr.left == left){
                        curr.left = left.left;
                        if (left.left!=null){
                            left.left.parent = curr;
                        }
                    }else{
                        left.parent.right = left.left;
                        if (left.left!=null){
                            left.left.parent = left.parent;
                        }
                    }
                }
            }
            public void mergeRight(TreeNode right, TreeNode curr){
                if (right == null) return;
                if (curr.interval.end+1>=right.interval.start){
                    curr.interval.end = right.interval.end;
                    decrementPathCount(right);
                    if(curr.right == right){
                        curr.right = right.right;
                        if (right.right!=null){
                            right.right.parent = curr;
                        }
                    }else{
                        right.parent.left = right.right;
                        if (right.right!=null){
                            right.right.parent = right.parent;
                        }
                    }
                }
            }
            public void rebalance(){
                // int leftCount = this.left == null ? 0:this.left.count;
                // int rightCount = this.right == null ? 0:this.right.count;
                // // if (leftCount> rightCount+1){
                // //     if (this.parent != null){
                // //         TreeNode superParent = this.parent;
                // //     }else{
                        
                // //     }
                    
                // // }
            }
            public boolean insert(int val){
                TreeNode curr = this;
                if (val == curr.interval.start-1){
                    this.interval.start = val;
                    TreeNode left = findLeft();
                    mergeLeft(left, this);
                }else if (val == curr.interval.end+1){
                    this.interval.end = val;
                    TreeNode right = findRight();
                    mergeRight(right, this);
                }else if (val<curr.interval.start){
                    if (this.left == null){
                        this.left = new TreeNode(1,new Interval(val,val));
                        this.left.parent=this;
                        return true;
                    }else{
                        boolean attempt = this.left.insert(val);
                        if (attempt){
                            count++;
                            rebalance();
                        }
                    }
          
                }else if (val>curr.interval.end){
                    if (this.right == null){
                        this.right = new TreeNode(1,new Interval(val,val));
                        this.right.parent=this;
                        return true;
                    }else{ 
                        boolean attempt =this.right.insert(val);
                        if (attempt){
                            count++;
                            rebalance();
                        }
                    }
                   
                }
                return false;
    
            }
            public List<Interval> inorder(TreeNode root){
                List<Interval> result = new ArrayList<>();
                if (root ==null){
                    return result;
                }
                TreeNode curr = root;
                Stack<TreeNode> stk = new Stack<>();
                while(curr!= null || !stk.isEmpty()){
                    if(curr!=null){
                        stk.add(curr);
                        curr = curr.left;
                        
                    }else{
                        TreeNode temp = stk.pop();
                        result.add(new Interval(temp.interval.start,temp.interval.end));
                        curr = temp.right;
                    }
                }
                return result;
            }
        }
        TreeNode root;
        /** Initialize your data structure here. */
        public SummaryRanges() {
          root = null;
        }
        
        public void addNum(int val) {
            if (root == null){
                this.root = new TreeNode(1, new Interval(val,val));
            }else{
                root.insert(val);
            }
            
        }
        
        public List<Interval> getIntervals() {
            return (new TreeNode(-1,null)).inorder(root);
        }
    }
    
    /**
     * Your SummaryRanges object will be instantiated and called as such:
     * SummaryRanges obj = new SummaryRanges();
     * obj.addNum(val);
     * List<Interval> param_2 = obj.getIntervals();
     */

Log in to reply
 

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