博文中会简要介绍Leetcode P0272题目分析及解题思路。
“Closest Binary Search Tree Value II”是一道稍难的题目，同时也是p0270的衍生题。
Given the root of a binary search tree, a target value, and an integer
k, return thekvalues in the BST that are closest to the target. You may return the answer in any order.You are guaranteed to have only one unique set of
kvalues in the BST that are closest to the target.
如何思考这道题？
一般来说，如果发现这道题需要我们寻找k个指定的数，如最接近目标数的k个数，最小的k个数等等，我们应当想到利用堆结构（Heap）来解题。堆结构（Heap）可以帮助我们很方便地维护我们所寻找到的k个数，并且在O(logn)的时间内进行修改。
类似地，如果要求我们寻找到第k个指定的数，那么除了想到利用堆结构之外，也要想到可以使用二分搜索，即每次排除剩余的一半或者找到满足条件的k/2个数（此时k在迭代中二分缩小）。
基本思路
这道题的思路其实比较直接明了。
遍历一遍给定的二叉树，同时维护一个大小为k的最大堆maxHeap，最大堆maxHeap中存储的项是键值对：键是离目标的距离，用以排序；值是数本身，用以返回结果。
最后再将maxHeap中的所有项存入一个数组中即可。
以下是Java的题解代码实现。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
this.maxHeap = new PriorityQueue<>((x, y) -> {
return Double.compare(y.getKey(), x.getKey());
});
this.dfs(root, target, k);
List<Integer> ret = new ArrayList<>();
while (!this.maxHeap.isEmpty()) {
ret.add(this.maxHeap.poll().getValue());
}
return ret;
}
private PriorityQueue<Pair<Double, Integer>> maxHeap = null;
private void dfs(TreeNode cur, double target, int k) {
if (cur == null)
return;
double diff = Math.abs(target-cur.val);
if (this.maxHeap.size() >= k) {
if (diff < this.maxHeap.peek().getKey()) {
this.maxHeap.poll();
this.maxHeap.offer(new Pair(diff, cur.val));
}
}
else {
this.maxHeap.offer(new Pair(diff, cur.val));
}
this.dfs(cur.left, target, k);
this.dfs(cur.right, target, k);
return;
}
}
以下是C++的题解代码实现。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
template<class K, class V>
struct PairComparator {
bool operator() (pair<K, V> x, pair<K, V> y) const {
return x.first < y.first;
}
};
class Solution {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
_Dfs(root, target, k);
vector<int> ret;
while (!_max_heap.empty()) {
ret.push_back(_max_heap.top().second);
_max_heap.pop();
}
return ret;
}
private:
priority_queue<pair<double, int>, vector<pair<double, int>>, PairComparator<double, int>> _max_heap;
void _Dfs(TreeNode *cur, double target, int k) {
if (!cur)
return;
double diff = abs(target-cur->val);
if (_max_heap.size() >= k) {
if (diff < _max_heap.top().first) {
_max_heap.pop();
_max_heap.emplace(diff, cur->val);
}
}
else {
_max_heap.emplace(diff, cur->val);
}
_Dfs(cur->left, target, k);
_Dfs(cur->right, target, k);
return;
}
};