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%的
Mistakes:
要注意root value不是先插入的
***********上面思路的简化版本***********
No comments:
Post a Comment