05 August 2008
Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
Note:
Example:
1
2
3
4
5
6
7
8
9
Input: root = [4,2,5,1,3], target = 3.714286, and k = 2
4
/ \
2 5
/ \
1 3
Output: [4,3]
Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
中序遍历，维护一个LinkedList，从最左端开始遍历，达到k个后，新来的元素跟最早加入的元素对比看哪个更近，如果新来的元素更近就剔出最早的元素，这一点很重要，为什么是跟最早的元素比较？设想如果target离最早的元素很近，那么新来的元素只会比最后加入的元素离target更远，更不会比最早的元素近；如果target离最早的元素很远（往右子树方向走），那么这时候就应该剔出最早的元素。所以新来的元素跟最早进入linkedlist的元素对比是正确的，所以如果新来的元素不比最早的元素近，那么直接返回当前的k个，因为BST后面的元素只会更远了。
这道题不用LinkedList，可以用List或者PriorityQueue，但试了下感觉麻烦一些
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
LinkedList<Integer> results; // 这里需要用到LinkedList实现而不是List接口，才能使用下面的一些API
public List<Integer> closestKValues(TreeNode root, double target, int k) {
results = new LinkedList<>();
inOrder(root, target, k);
return results;
}
private void inOrder(TreeNode node, double target, int k) {
if (node == null) {
return;
}
//先中序遍历到最左边
inOrder(node.left, target, k);
if (k > results.size()) { // 还未到kk个
results.add(node.val);
} else { // 已有k个candidates，开始检查
if (Math.abs(node.val - target) < Math.abs(results.peekFirst() - target)) {
// 剔除最先加入的元素，仔细想想，如果新来的元素比最先加入的元素离target更近，那么最先加入的元素一定是最远的一个
results.pollFirst();
results.add(node.val);
} else {// 如果新来的元素不比最先加入的元素近，根据BST的特征，后面（右子树）的元素不用继续查了
return;
}
}
// 不够k个再遍历右子树
inOrder(node.right, target, k);
}
}
Follow up是如果给定的二叉树是平衡的，可不可以将时间复杂度降到O(logn)，利用两个栈来保存target的前驱和后继, 而且两个栈顶的元素保存的是当前距离target最近的前驱和后继, 这样就可以每次取到距离target最近的值. 这种时间复杂度可以达到O(logn).