Table of Contents
Leetcode 272. Closest Binary Search Tree Value II
Problem
Given the root
of a binary search tree, a target
value, and an integer k
, return the k
values 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 k
values in the BST that are closest to the target
.
Example 1:
Input: root = [4,2,5,1,3], target = 3.714286, k = 2 Output: [4,3]
Example 2:
Input: root = [1], target = 0.000000, k = 1 Output: [1]
Constraints:
- The number of nodes in the tree is
n
. 1 <= k <= n <= 104
.0 <= Node.val <= 109
-109 <= target <= 109
Follow up: Assume that the BST is balanced. Could you solve it in less than O(n)
runtime (where n = total nodes
)?
Solution
The straight forward solution of this problem is to use a heap (a.k.a priority queue).
We can run an inorder traversal of the tree. That way, we will get the values in sorted order. During that process, we can save the absolute difference between target and node value to the heap. Also, we need to have the node value. That’s why it is good to have a pair of absolute difference and node value [something like {difference, val}] in the heap. Also, when we push those pairs in heap, we will check if heap size is greater than K. If it is, we will remove the last element from heap.
Below is the code that implements this idea.
C++ Code
/** * 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: void inorder(TreeNode* root, double target, int k, priority_queue<pair<double, int>>& pq){ if(root == NULL) return; inorder(root->left, target, k, pq); pq.push({abs(target - root->val), root->val}); if(pq.size() > k) pq.pop(); inorder(root->right, target, k, pq); } vector<int> closestKValues(TreeNode* root, double target, int k) { vector<int> ans; if(root == NULL) return ans; priority_queue<pair<double, int>> pq; inorder(root, target, k, pq); while(!pq.empty()){ ans.push_back(pq.top().second); pq.pop(); } return ans; } };
Conclusion
Hope you understood this solution. If not, please comment below which part was not so clear.
Happy Coding! 🙂
To the foolishhungry.com webmaster, Keep sharing your knowledge!
Apoiar ferramentas de apostas e estar equipado com uma plataforma diversificada de transações financeiras, a 20Bet oferece suporte tangível aos jogadores. Este é um lugar onde eles podem apostar com dinheiro real, respaldados por concorrentes de diversas disciplinas esportivas. 20bet
Dear foolishhungry.com admin, Your posts are always a great source of information.
Hello foolishhungry.com admin, Great content!
Hi foolishhungry.com webmaster, Your posts are always well-supported by research and data.
Hi foolishhungry.com administrator, Great post!
Hello foolishhungry.com admin, Thanks for the well written post!
Dear foolishhungry.com webmaster, You always provide clear explanations and definitions.
Hello foolishhungry.com webmaster, You always provide practical solutions and recommendations.
Hi foolishhungry.com webmaster, Thanks for the in-depth post!
Hello foolishhungry.com admin, Keep sharing your knowledge!
Due to the excellent quality of the content on this website and the fact that its administrator is actively working, it is certain to gain popularity very soon.
Dear foolishhungry.com owner, You always provide great examples and real-world applications.
Your point of view caught my eye and was very interesting. Thanks. I have a question for you. https://www.binance.com/cs/register?ref=B4EPR6J0
Hello foolishhungry.com webmaster, You always provide great resources and references.
This is my first brief visit, and I’m delighted to have everything in one location.
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me. https://accounts.binance.com/pt-BR/register?ref=S5H7X3LP
naturally like your web site however you need to take a look at the spelling on several of your posts. A number of them are rife with spelling problems and I find it very bothersome to tell the truth on the other hand I will surely come again again.
Dear foolishhungry.com administrator, You always provide clear explanations and step-by-step instructions.
Thank you for your sharing. I am worried that I lack creative ideas. It is your article that makes me full of hope. Thank you. But, I have a question, can you help me? https://accounts.binance.com/zh-TC/register?ref=T7KCZASX
I don’t think the title of your article matches the content lol. Just kidding, mainly because I had some doubts after reading the article.
I loved as much as youll receive carried out right here The sketch is tasteful your authored material stylish nonetheless you command get bought an nervousness over that you wish be delivering the following unwell unquestionably come more formerly again since exactly the same nearly a lot often inside case you shield this hike
I was recommended this website by my cousin I am not sure whether this post is written by him as nobody else know such detailed about my difficulty You are wonderful Thanks
Hi foolishhungry.com administrator, You always provide clear explanations and step-by-step instructions.