Problem Statement
leetcode problem link
Brute Force [Accepted]
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def closestValue(self, root: Optional[TreeNode], target: float) -> int:
def dfs(node, curr, diff):
if not node:
return curr
curr_diff = abs(node.val - target)
if diff > curr_diff:
curr = node.val
diff = curr_diff
elif diff == curr_diff:
curr = min(curr, node.val)
diff = curr_diff
if target == node.val:
return node.val
if target < node.val:
return dfs(node.left, curr, diff)
elif target > node.val:
return dfs(node.right, curr, diff)
return dfs(root, root.val, float('inf'))
Editorial
Approach 1: Recursive Inorder + Linear search, O(N) time
class Solution:
def closestValue(self, root: TreeNode, target: float) -> int:
def inorder(r: TreeNode):
return inorder(r.left) + [r.val] + inorder(r.right) if r else []
return min(inorder(root), key = lambda x: abs(target - x))
Approach 2: Iterative Inorder, O(k) time
class Solution:
def closestValue(self, root: TreeNode, target: float) -> int:
stack, pred = [], float('-inf')
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
if pred <= target and target < root.val:
return min(pred, root.val, key = lambda x: abs(target - x))
pred = root.val
root = root.right
return pred
Approach 3: Binary Search, O(H) time
class Solution:
def closestValue(self, root: TreeNode, target: float) -> int:
closest = root.val
while root:
closest = min(root.val, closest, key = lambda x: (abs(target - x), x))
root = root.left if target < root.val else root.right
return closest
