O(nlgk) solution using binary search tree (java)


  • 3
    F

    public class Solution {
    class TreeNode{
    long val;
    TreeNode left;
    TreeNode right;
    public TreeNode(long x) {
    val = x;
    }
    }

    private TreeNode add(TreeNode root, TreeNode nNode) {
        if(root == null) {
            return nNode;
        }
        else if(root.val < nNode.val) {
            root.right = add(root.right, nNode);
            return root;
        }
        else {
            root.left = add(root.left, nNode);
            return root;
        }
    }
    
    private TreeNode delete(TreeNode root, TreeNode dNode) {
        if(root == null) {
            return null;
        }
        else if(root.val < dNode.val) {
            root.right = delete(root.right, dNode);
            return root;
        }
        else if(root.val > dNode.val) {
            root.left = delete(root.left, dNode);
            return root;
        }
        else if(root == dNode) {
             if(dNode.left == null && dNode.right == null) return null;
             else if(dNode.left != null && dNode.right == null) return dNode.left;
             else if(dNode.right != null && dNode.left == null) return dNode.right;
             else {
                 TreeNode p = dNode.right;
                 while(p.left != null) p = p.left;
                 dNode.right = delete(dNode.right, p);
                 p.left = dNode.left;
                 p.right = dNode.right;
                 return p;
             }
        }
        else {
            return root;
        }
    }
    
    private boolean search(TreeNode root, long val, int t) {
        if(root == null) {
            return false;
        }
        else if(Math.abs((root.val - val)) <= t) {
            return true;
        }
        else if((root.val - val) > t) {
            return search(root.left, val, t);
        }
        else {
            return search(root.right, val, t);
        }
    }
    
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(k < 1 || t < 0 || nums.length <= 1) {
            return false;
        }
        int len = nums.length;
        TreeNode[] map = new TreeNode[len];
        map[0] = new TreeNode((long)nums[0]);
        TreeNode root = null;
        root = add(root, map[0]);
        for(int i = 1; i < len; i++) {
            if(search(root, (long)nums[i], t)) {
                return true;
            }
            map[i] = new TreeNode((long)nums[i]);
            if(i - k >= 0) {
                root = delete(root, map[i-k]);
            }
            root = add(root, map[i]);
        }
        return false;
    }
    

    }


  • 0
    J

    @fatsheep9146 How are you ensuring that BST is balanced ?


Log in to reply
 

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