Java 3ms Clean Solution, Only one Queue, O(n), no assumption on balanced tree


  • 1
    Y

    The idea is fairly simple and similar to search for Kth element in the BST.
    I did the inorder traversal of the BST. The inorder traversal is actually a sorted sequence. While performing traversal, keep adding elements into Queue until it reached size of K. When it reached size of K, compare the current value difference to the target to the first element value different to the target. If it is smaller than the first one, poll the first one and add the current one. If it is greater than the first one, terminate the traversal.

    private Queue<Integer> results = null;
    private boolean end = false;
    
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        if (k <= 0) {
            return new ArrayList<Integer>();
        }
        results = new ArrayDeque<>(k);
        end = false;
        helper(root, target, k);
        return new ArrayList<Integer>(results);
    }
    
    public void helper(TreeNode node, double target, int k) {
        if (node == null || end) {
            return;
        }
        
        helper(node.left, target, k);
        if (results.size() < k) {
            results.add(node.val);
        } else {
            int first = results.peek();
            int val = node.val;
            double diff1 = Math.abs(target - (double) first);
            double diff2 = Math.abs(target - (double) val);
            if (diff1 > diff2) {
                results.poll();
                results.add(val);
            } else {
                end = true;
                return;
            }
        }
        helper(node.right, target, k);
    }

  • 0
    I

    When queue is size k, why do you compare value of first node in queue to current node?


Log in to reply
 

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