Java BST


  • 0
    Y

    BST solution should TLE in worst case but it now beats 99% solutions... Test case is not large enough.

    public class Solution {
        boolean debug = false;
        public double[] medianSlidingWindow(int[] nums, int k) {
            BSTNode root = null;
            double[] ans = new double[nums.length - k + 1];
            for (int i = 0; i < nums.length; i ++) {
                root = insert(nums[i], root);
                if (i - k >= 0) delete(nums[i - k], root);
                if (debug) {
                    System.out.println("i = " + i + ", nums[i] = " + nums[i]);
                    traverse(root);
                    System.out.println();
                }
                if (i < k - 1) continue;
                if (k % 2 == 1) ans[i - (k - 1)] = search(k / 2 + 1, root);
                else ans[i - (k - 1)] = (1.0 * search(k / 2 + 1, root) + 1.0 * search(k / 2, root)) / 2;
            }
            return ans;
        }
        
        public BSTNode insert(int v, BSTNode root) {
            if (root == null) return new BSTNode(v);
            if (root.val == v) { root.dup ++; return root; }
            else if (root.val > v) { root.less ++; root.left = insert(v, root.left); return root; }
            else { root.right = insert(v, root.right); return root; }
        }
        
        public void delete(int v, BSTNode root) {
            if (root == null) return;
            if (root.val == v) { root.dup --; }
            else if (root.val > v) { root.less --; delete(v, root.left);}
            else { delete(v, root.right); }
        }
        
        public int search(int n, BSTNode root) {
            return helper(n, root, 0);
        }
        
        public int helper(int n, BSTNode root, int preSum) {
            if (n > preSum + root.dup + root.less) return helper(n, root.right, preSum + root.dup + root.less);
            else if (n > preSum + root.less) return root.val;
            else return helper(n, root.left, preSum);
        }
        
        public void traverse(BSTNode root) {
            if (root == null) return;
            traverse(root.left);
            System.out.println("val = " + root.val + ", dup = " + root.dup + ", less = " + root.less);
            traverse(root.right);
        }
    }
    
    class BSTNode {
        int val;
        int dup;
        int less;
        BSTNode left, right;
        public BSTNode(int v) {
            val = v;
            dup = 1;
            less = 0;
            left = null;
            right = null;
        }
    }
    

Log in to reply
 

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