# 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.val-target) == 0: self.res = root.val return # backtracking if abs(root.val-target) < 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(x-target)) # 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(x-target))
root = TreeNode(2) root.left = TreeNode(1) target = sys.maxint
your third solution (the BST one) incorrectly returns sys.maxint.
Yes, you are correct, extra checking should be added. It can be fixed by adding: if not node:
Not sure it should be a valid test case, though. This here is Python, but in general the tree values are just 32-bit ints, right? I then find it odd to ask for a 64-bit 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 (32-bit 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 distance-to-target 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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.