# works for normal binary tree
def closestValue1(self, root, target):
if not root:
return 0
self.res = root.val
self.findClosest(root, target)
return self.res
def findClosest(self, root, target):
if root:
if abs(root.valtarget) == 0:
self.res = root.val
return # backtracking
if abs(root.valtarget) < abs(self.res  target):
self.res = root.val
self.findClosest(root.left, target)
self.findClosest(root.right, target)
# works for normal binary tree
def closestValue2(self, root, target):
if not root:
return sys.maxint
if not root.left and not root.right:
return root.val
l = self.closestValue(root.left, target)
r = self.closestValue(root.right, target)
return min([root.val, l, r], key=lambda x:abs(xtarget))
# works for binary search tree
def closestValue(self, root, target):
if not root:
return sys.maxint
if not root.left and not root.right:
return root.val
node = root.right if target > root.val else root.left
if not node:
return root.val
tmp = self.closestValue(node, target)
return min((tmp, root.val), key=lambda x:abs(xtarget))
Python different recursive solutions.


Not sure it should be a valid test case, though. This here is Python, but in general the tree values are just 32bit ints, right? I then find it odd to ask for a 64bit value.
Btw, while my own solutions still correctly solve the added test case
[2,1], 9223372036854775807.0
, they'd fail[1,null,2], 9223372036854775807.0
because at that scale the difference to 1 and 2 is lost:>>> 9223372036854775807.0  1 == 9223372036854775807.0  2 True
My solutions only still work because they encounter the correct answer first, as it's the root value. Allowing such large targets likely breaks everybody's solutions so far. We can all fix it by capping target with "small" values, like doing
target = max(min(target, 2**32), 2**32)
before anything else, but that's a bit ugly, especially for recursive solutions, which would cap target again and again unless we write some kind of wrapper.
I think it's unnecessarily "mean" and it would be a good idea if the problem limited target to the possible tree value range (32bit integer range) because it makes little sense to ask for something far outside.

Ahaha, I forgot I had thought of a different fix before I went to sleep last night, one that some of my solutions (unintentionally) already use :) (and caikehe's third does, too). In case of a distancetotarget tie between previous closest value and new value (lower in the tree), simply prefer the new value, not the previous. That way, if the target is very large, the result will still be correct. Works for large negative target as well.
So yeah, that's actually quite neat and doesn't require such an ugly additional fix, so I'm now less against large targets :)
Edit: Fixed my remaining wrong ones now.