My java solution using BST, I am not sure is there any bugs even it is AC


  • 0
    E
        public class Solution {
    	public  class TreeNode {
            int val;
            int idx;
            TreeNode left;
            TreeNode right;
    
            public TreeNode(int v, int i) {
                this.val = v;
                this.idx = i;
                left = null;
                right = null;
            }
        }
    
         TreeNode root = null;
    
        public  boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if (nums == null || nums.length == 0)
                return false;
    
            for (int i = 0; i < nums.length; i++) {
                if (root == null)
                    root = new TreeNode(nums[i], i);
                else {
                    if (contain(root, nums[i], i, k, t))
                        return true;
                }
            }
            return false;
        }
    
        public boolean contain(TreeNode temp, int v, int i, int k, int t) {
            TreeNode cur = temp;
            TreeNode pre = cur;
            while (cur != null) {
                pre = cur;
                if (v >= cur.val) {
                    if(v>0 && cur.val<0 && v>cur.val+Integer.MAX_VALUE)
                            return false;
                    if (Math.abs(v - cur.val) <= t && Math.abs(cur.idx - i) <= k)
                        return true;
                    cur = cur.right;
                } else {
                    if(v<0 && cur.val>0 && cur.val>v+Integer.MAX_VALUE)
                            return false;
                    if (Math.abs(v - cur.val) <= t && Math.abs(cur.idx - i) <= k)
                        return true;
                    cur = cur.left;
                }
            }
    
            if  (v >= pre.val) {
                TreeNode node = new TreeNode(v, i);
                if(Math.abs(v - root.val) <= t) {
                    node.left = root;
                    root = node;
                }
    
                else {
                    pre.right = node;
                }
            }
            else {
                TreeNode node = new TreeNode(v, i);
                if(Math.abs(v - root.val) <= t) {
                    node.right = root;
                    root = node;
                }
    
                else {
                    pre.left = node;
                }
            }
            return false;
        }
    }

Log in to reply
 

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