272. Closest Binary Search Tree Value II
Hard
Two Pointers
Stack
Tree
Depth-First Search
Binary Search Tree
Heap (Priority Queue)
Binary Tree
Description
From doocs/leetcode
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)?
Hints
Hint 1
Consider implement these two helper functions:
<ol type="i"><li><code>getPredecessor(N)</code>, which returns the next smaller node to N.</li>
<li><code>getSuccessor(N)</code>, which returns the next larger node to N.</li>
</ol>
Hint 2
Try to assume that each node has a parent pointer, it makes the problem much easier.
Hint 3
Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
Hint 4
You would need two stacks to track the path in finding predecessor and successor node separately.
Similar Questions
Statistics
Acceptance
61.0%
Submissions
225,447
Accepted
137,462