# O(n) Java Solution

• I have to say that it takes me several days to figure out this solution;
My thought is actually pretty simple, suppose I get the whole sorted values, n elements, how can I get the k closest values?
In order to get the sorted values, an inorder visit will work, which takes O(n) time;
the next step is to get the K closest values; first thing is the find the most closest value; which is actually pretty easy, by comparing abs one by one, stoping at the index which increase the difference; it also takes O(n) time; second, we can use two pointers, i and j, at two ends of the range; step each pointer by comparing the abs difference at the next position;
sorry for my poor English; I guess the code is more clear to understand;

``````public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> values = new ArrayList<>();
visit(root, values);

return helper(target, k, values);
}

public List<Integer> helper(double target, int k, List<Integer> values) {
int x = 0;
double minDiff = abs(target, values.get(x));

for (x = 1; x < values.size(); x++) {
double diff = abs(target, values.get(x));
if (diff > minDiff) {
break;
}
minDiff = diff;
}

x = x - 1;

int i = x, j = x;

while (j - i + 1 < k) {
double diffOne = Double.MAX_VALUE;
if (i > 0) {
diffOne = abs(target, values.get(i - 1));
}
double diffTwo = Double.MAX_VALUE;
if (j < values.size() - 1) {
diffTwo = abs(target, values.get(j + 1));
}

if (diffOne < diffTwo) {
i -= 1;
} else {
j += 1;
}
}

return values.subList(i, j + 1);
}

private double abs(double a, int b) {
return Math.abs(a - b);
}

private void visit(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}

visit(root.left, list);