very short O(n) solution based on inorder traversal and two-pointers with explanation


  • 0
    Q
    // if k is large, we can use this O(n)solution
    // after inorder traversal, we get a sorted array, we can either get the closest number(O(logn) time) and check adjacent elements one by one (O(k) time)
    // or eliminate elements from left boundary and right boundary(O(n - k)) like the implementation below
    // a short proof: since the final result must be a consecutive sub-suquence, and when the number of current available elements is larger than k, 
    // if we pick current left boundary, we cannot pick current right boundary, 
    // in other words, they are mutual exclusive. 
    // Therefore if left is better than right, left is kept and right must be eliminated. Therefore we can use this two-pointers way.
    
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        LinkedList<Integer> v = new LinkedList<Integer>();
        inOrder(root, v);
        while(v.size() > k){
            if (Math.abs(v.peekFirst() - target) <= Math.abs(v.peekLast() - target)) v.removeLast();
            else v.removeFirst();
        }
        return v; 
    }
    private void inOrder(TreeNode root, List<Integer> v){
        if (root == null) return;
        inOrder(root.left, v);
        v.add(root.val);
        inOrder(root.right, v);
    }

Log in to reply
 

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