Solution with self-written BST


  • 0
    J
    public class Solution {
    static int T=5;
    private class BST{
        int val;
        BST left=null, right=null;
        public BST(int v){
            this.val = v;
        }
        public boolean insert(int v){ // modified for the problem
            if(Math.abs((long)v-(long)this.val)<=Solution.T) return true;//if difference is less than T: return true
            if (v<this.val){
                if(this.left!=null) return this.left.insert(v);
                else this.left = new BST(v);}
            else{
                if(this.right!=null) return this.right.insert(v);
                else this.right = new BST(v);}
            return false;
        }
        public int minVal(){
            BST nd = this;
            while(nd.left!=null) nd = nd.left;
            return nd.val;
        }
        public void remove(int v, BST parent){
            if(this.val==v){
                if(this.left==null && this.right==null){
                    if(parent.left==this) parent.left = null;
                    else parent.right=null;
                }
                else if(this.left==null){
                    if(parent.left==this) parent.left = this.right;
                    else parent.right=this.right;
                }
                else if(this.right==null){
                    if(parent.left==this) parent.left = this.left;
                    else parent.right=this.left;
                }
                else{//*if has 2 children: 
                    int rightmin = this.right.minVal();
                    this.val = rightmin;//first change nd to the min val in right subtree
                    this.right.remove(rightmin, this);//then remove this val in right subtree
                }
            }
            else if(this.val>v) this.left.remove(v, this);
            else this.right.remove(v, this);
        }
    }// class BST
    
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(nums==null || nums.length<=1) return false;
        if(k==0) return false;
        BST root = new BST(nums[0]);
        Solution.T = t;
        for(int i=1;i<nums.length;i++){
            int v = nums[i];
            if(root.insert(v)) return true;
            if(i-k>=0) {
                BST auxroot = new BST(Integer.MAX_VALUE);
                auxroot.left = root;
                root.remove(nums[i-k], auxroot);
                root = auxroot.left;
            }
        }
        return false;
    }//containsNearbyAlmostDuplicate()
    

    }


Log in to reply
 

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