Simple and fast Java method based on the Closest Binary Search Tree Value I with some explainations


  • 1
    R
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
             List<Integer> tree = new ArrayList<Integer>();
             inorder(root,tree);//use inorder to reserve the tree
             int size = tree.size();
             
             int key = closestValue(root,target);//use the method of closest binary search tree value I to find the key value
             //since other closest value are around this key value
             
             List<Integer> res = new ArrayList<Integer>();
             res.add(key);
             
             int keyIdx = tree.indexOf(key);//use two pointers to find the other closest value
             int left = keyIdx - 1, right = keyIdx + 1;
             while(res.size() < k && left >= 0 && right < size){
                 if(Math.abs(tree.get(left) - target) < Math.abs(tree.get(right) - target)){
                     res.add(tree.get(left--));
                 }else{
                     res.add(tree.get(right++));
                 }
                    
             }
             //deal with some corner cases, eg : [2,1], 4.3333,2
             while(res.size() < k && left >= 0)
                res.add(tree.get(left--));
             while(res.size() < k && right < size)
                res.add(tree.get(right++));
            
             return res;
        }
        
        public int closestValue(TreeNode root, double target){
            int val = root.val;
            while(root != null){
                if(Math.abs(target - root.val) < Math.abs(target - val)){
                    val = root.val;
                }
                
                root = root.val < target ? root.right : root.left;
            }
            return val;
        }
        
        public void inorder(TreeNode root, List<Integer> res){
            if(root.left != null)
                inorder(root.left,res);
            res.add(root.val);
            if(root.right != null)
                inorder(root.right,res);
        }
    

    The idea is based on the closest value 1, and the speed can beat more than 80%


  • 0
    I

    Is this ok solution to give in interview? I thought they would want less than O(N) solution


Log in to reply
 

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