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

• ``````// 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) {
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);