15ms java solution with BST


  • 1
    J

    I defined a simple BST data structure, too complicate if writing a balanced BST. I didn't include parent node in TreeNode so the implementation is quite long, sorry about that.

    private static class BSTree{
        private static class TreeNode{
            private TreeNode left = null, right = null;
            private int id = 0;
            public TreeNode(int i, TreeNode l, TreeNode r){
                id = i;
                left = l;
                right = r;
            }
        }
        private TreeNode root = null;
        public BSTree(){}
        public int add(int n){
            TreeNode newest = new TreeNode(n, null, null);
            if(root == null){
                root = newest;
                return -1;
            }
            TreeNode walk = root;
            if(walk.id == n)    return 0;
            int min = Integer.MAX_VALUE;
            while(walk != null){
                min = Math.min(Math.abs(walk.id - n), min);
                if(walk.left == null && walk.id > n){
                    walk.left = newest;
                    return min;
                }
                else if(walk.right == null && walk.id < n){
                    walk.right = newest;
                    return min;
                }
                else if(walk.id > n)    walk = walk.left;
                else if(walk.id < n)    walk = walk.right;
            }
            return -1;
        }
        public void remove(int n){
            if(root.id == n){
                root = recover(root);
                return;
            }
            TreeNode walk = root;
            while(walk != null){
                if(walk.left != null && walk.left.id == n){
                    walk.left = recover(walk.left);
                    return;
                }
                else if(walk.right != null && walk.right.id == n){
                    walk.right = recover(walk.right);
                    return;
                }
                else if(walk.id > n)
                    walk = walk.left;
                else if(walk.id < n)
                    walk = walk.right;
            }
        }
        public TreeNode recover(TreeNode rt){
            if(rt.left == null) return rt.right;
            else if(rt.right == null)   return rt.left;
            TreeNode walk = rt.right;
            if(walk.left == null){
                walk.left = rt.left;
                return walk;
            }
            while(walk.left.left != null){
                walk = walk.left;
            }
            TreeNode temp = walk.left;
            walk.left = walk.left.right;
            temp.left = rt.left;
            temp.right = rt.right;
            return temp;
        }
    }
    

    Then implemented the algorithm with maintaining a size k+1 BST, and searched each incoming element to get a minimum subtraction.

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        BSTree tree = new BSTree();
        for(int i = 0; i < nums.length; i++){
            if(i > k)   tree.remove(nums[i-k-1]);
            int dist = tree.add(nums[i]);
            if(dist >= 0 && dist <= t)  return true;
        }
        return false;
    }

  • 0
    J

    Add python version:

    class TreeNode(object):
        def __init__(self):
            self.val = None
            self.left = None
            self.right = None
        
    class BSTree(object):
        def __init__(self):
            self.root = TreeNode()
           
        def insert(self, n):
            new_node = TreeNode()
            new_node.val = n
            if self.root.val == None:
                self.root = new_node
                return -1
                   
            node = self.root
            min_val = float("inf")
            while node != None:
                if node.val == n:
                    return 0
                min_val = min(min_val, abs(node.val - n))
                if node.left is None and node.val > n:
                    node.left = new_node
                    return min_val
                elif node.right is None and node.val < n:
                    node.right = new_node
                    return min_val
                elif node.val > n:
                    node = node.left
                elif node.val < n:
                    node = node.right
            return -1
                
        def delete(self, n):
            if self.root.val == n:
                self.root = self.rotate(self.root)
                return
            node = self.root
            last_node = None
            is_left = False
            while node:
                if node.val == n:
                    if is_left:
                        last_node.left = self.rotate(node)
                    else:
                        last_node.right = self.rotate(node)
                    return
                last_node = node
                if node.val > n:
                    node = node.left
                    is_left = True
                elif node.val < n:
                    node = node.right
                    is_left = False
          
        def rotate(self, del_node):
            """
            return the root of the subtree after deleting del_node
            """
            if del_node.left is None:
                return del_node.right
            elif del_node.right is None:
                return del_node.left
                
            node = del_node.right
            if node.left is None:
                node.left = del_node.left
                return node
            while node.left.left is not None:
                node = node.left
            tmp_node = node.left
            node.left = node.left.right
            tmp_node.left = del_node.left
            tmp_node.right = del_node.right
            return tmp_node
                
    class Solution(object):
        def containsNearbyAlmostDuplicate(self, nums, k, t):
            if t < 0 or k < 1:
                return False
            nums_len = len(nums)
            tree = BSTree()
            for i in range(nums_len):
                if i > k:
                    tree.delete(nums[i-k-1])
                diff = tree.insert(nums[i])
                if diff >= 0 and diff <= t:
                    return True
            return False
    

Log in to reply
 

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