LeetCode Solutions
270. Closest Binary Search Tree Value
Time: $O(h)$ Space: $O(h)$
class Solution {
public:
int closestValue(TreeNode* root, double target) {
// If target < root->val, search left subtree
if (target < root->val && root->left) {
const int left = closestValue(root->left, target);
if (abs(left - target) < abs(root->val - target))
return left;
}
// If target > root->val, search right subtree
if (target > root->val && root->right) {
const int right = closestValue(root->right, target);
if (abs(right - target) < abs(root->val - target))
return right;
}
return root->val;
}
};
class Solution {
public int closestValue(TreeNode root, double target) {
// If target < root.val, search left subtree
if (target < root.val && root.left != null) {
final int left = closestValue(root.left, target);
if (Math.abs(left - target) < Math.abs(root.val - target))
return left;
}
// If target > root.val, search right subtree
if (target > root.val && root.right != null) {
final int right = closestValue(root.right, target);
if (Math.abs(right - target) < Math.abs(root.val - target))
return right;
}
return root.val;
}
}
class Solution:
def closestValue(self, root: Optional[TreeNode], target: float) -> int:
# If target < root.val, search left subtree
if target < root.val and root.left:
left = self.closestValue(root.left, target)
if abs(left - target) < abs(root.val - target):
return left
# If target > root.val, search right subtree
if target > root.val and root.right:
right = self.closestValue(root.right, target)
if abs(right - target) < abs(root.val - target):
return right
return root.val