LeetCode 272. Closest Binary Search Tree Value II
Problem Clarification
Implement a function closestKValues(root: TreeNode, target: float, k: int) -> List[int]
, which finds k values in a BST (binary search tree) that are closest to a target value.
assume k is always valid and k <= total nodes
the k values are not required to be ordered
Analysis
- Get sorted list from the BST (InOrder Traversal, time complexity $\Theta(N)$, space complexity $\Theta(N)$), then get the length-k slice:
- a. Loop from the beginning of the list, update the closest k values list
ans
, stop whenans
is full (length k) andabs(list_item - target) > abs(ans[0] - target)
, time complexity best $\Theta(k)$, worst $\Theta(N)$ -> total time comlexity $O(N)$ - b. Truncate the sorted list from both ends, until it shrinks to length k, time complexity $O(N)$
- c. Use Binary Search to find the closest value to target, then expand to two directions, stop when found k values. Time complexity $\Theta(logN + k)$, total time complexity $O(N)$
- a. Loop from the beginning of the list, update the closest k values list
- No need to get the full sorted list beforehand, but rather get sorted element on the go, similar to 1a. Time complexity $O(N)$.
- (best time complexity) No need to acquire the sorted list to use binary search, but rather find the closest value in the raw BST, then expand to two directions
predecessors
andsuccessors
. Time complexity $O(logN + k)$ if BST is balanced, $O(N + k)$ if BST is totally unbalanced.
Code
- 1a
class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]: if not k: return [] def inorderTraversal(node): if not node: return [] return inorderTraversal(node.left) + [node.val] + inorderTraversal(node.right) ans = collections.deque() for num in inorderTraversal(root): if len(ans) < k: ans.append(num) else: if abs(num - target) < abs(ans[0] - target): ans.popleft() ans.append(num) return ans # sorted(ans, key=lambda x: abs(x - target))
- 2
class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]: if not k: return [] ans = collections.deque() def inorderTraversal(node, target, k, ans): if not node: return inorderTraversal(node.left, target, k, ans) if len(ans) < k: ans.append(node.val) elif abs(node.val - target) < abs(target - ans[0]): ans.popleft() ans.append(node.val) else: return inorderTraversal(node.right, target, k, ans) inorderTraversal(root, target, k, ans) return ans
- 3 delicate implementation, partly populate
predecessors
andsuccessors
stacks as the byproduct of finding target in the BST, then pop the next nearest value from either of the two stacks, and populate the stack incrementally on the go.class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]: predecessors, successors = [], [] while root: if root.val < target: predecessors.append(root) root = root.right else: successors.append(root) root = root.left def getPred(stack): largestSmaller = stack.pop() smaller = largestSmaller.left while smaller: stack.append(smaller) smaller = smaller.right return largestSmaller.val def getSucc(stack): smallestLarger = stack.pop() larger = smallestLarger.right while larger: stack.append(larger) larger = larger.left return smallestLarger.val ans = [] while k: k -= 1 if not predecessors: ans.append(getSucc(successors)) elif not successors: ans.append(getPred(predecessors)) elif target - predecessors[-1].val < successors[-1].val - target: ans.append(getPred(predecessors)) else: ans.append(getSucc(successors)) return ans