Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
Note:
- Given target value is a floating point.
- You may assume k is always valid, that is: k ≤ total nodes.
- You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Example:
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)?
A:
首先想到都弄到一个数组里，然后全部排序。 然而不是optimal
思路是找到k个比他小的， 和k个比他大的。 然后前后两头儿检查 删除一个。
O（ k + log N ) time, O(k) space
/**
* 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) {}
* };
*/
class Solution {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
deque<int> res;
// find up to k values, that smaller than(or equal to) target
find_k_smallerEq(root, target, k, res);
deque<int> resBigger;
find_k_bigger(root, target, k, resBigger);
for (auto v : resBigger) {
res.push_back(v);
}
while (res.size() > k) {
if (abs(res.front() - target) >= abs(res.back() - target)) {
res.pop_front();
}
else {
res.pop_back();
}
}
return vector<int>(res.begin(), res.end());
}
private:
void find_k_smallerEq(TreeNode* root, double target, const int k, deque<int>& res) {
if (not root || res.size() >= k)
return;
if (root->val > target) {
find_k_smallerEq(root->left, target, k, res);
return;
}
find_k_smallerEq(root->right, target, k, res);
if (res.size() < k)
res.push_front(root->val);
find_k_smallerEq(root->left, target, k, res);
}
void find_k_bigger(TreeNode* root, double target, const int k, deque<int>& res) {
if (not root || res.size() >= k) {
return;
}
if (root->val <= target) {
find_k_bigger(root->right, target, k, res);
return;
}
find_k_bigger(root->left, target, k, res);
if (res.size() < k)
res.push_back(root->val);
find_k_bigger(root->right, target, k, res);
}
};
Faster than 95.75%的
Intuition
To resolve this problem, we use an in-order traversal of the BST. The reason for this choice is that an in-order traversal of a BST yields the values in sorted order. As we traverse the tree, we compare the values of the nodes with the target value to determine how close they are to the target.
We use a deque (double-ended queue) to keep track of the closest values found so far. The deque maintains the k closest values in sorted order due to the nature of in-order traversal. Here's a step-by-step outline of the intuition:
- Perform an in-order traversal (left-root-right) because the BST's property guarantees sorted values.
- Use a deque of size
k to maintain the closest values to the target. We start by adding values to the deque until it is full. - Once the deque has
k elements, we compare the current value (as we continue in-order traversal) with the first element in the deque (the element that is the farthest from the target among those in the deque). If the current value is closer, we remove the first element and add the current value to the deque. - If we find a value that is not closer than the first element in the deque, we can stop the traversal. Since the values are sorted, all subsequent values will be even farther from the target.
- After completing the traversal, we return the contents of the deque as our result.
This approach efficiently finds the k closest values by leveraging the sorted nature of the BST and by keeping our list of candidates to a fixed size (k).
Mistakes：
要注意root value不是先插入的
***********上面思路的简化版本***********
