def closestValue(self, root, target): tmp = int(target + 0.5) gap = abs(root.val - target) ans = root while root: if tmp == root.val: return root.val elif tmp < root.val: if abs(root.val - tmp) < gap: gap = abs(root.val - tmp) ans = root root = root.left else: if abs(root.val - tmp) < gap: gap = abs(root.val - tmp) ans = root root = root.right return ans.val
Update: Solution got updated, this example is now solved correctly.
That's not correct, try this test case:
root = TreeNode(4) root.left = TreeNode(1) target = 3
Your solution returns 1 instead of 4.
yeah, Thanks for this comment, I also came up with the same problem before I ran it, and I have fixed it right now.
Sorry, new counter-example :-)
root = TreeNode(1500000000) root.left = TreeNode(1400000000) target = -1500000000
Your current solution returns 1500000000.
the above code is already the fixed for the first problem, but second problem is pointed by stefan... coming soon...lol
@StefanPochmann hahahahha, just change 2147483647 to 99999999999999, and it works again.. if you use larger number than 99999999999999, and it will be wrong again lol
@ruichang this code is the original version:
def closestValue(self, root, target): tmp = int(target + 0.5) while True: if tmp == root.val: return root.val elif tmp < root.val: if not root.left: return root.val root = root.left else: if not root.right: return root.val root = root.right
if you use larger number than 99999999999999
Good idea, let's use target=1e100, which is possible since it's a float :-)
root = TreeNode(1) root.right = TreeNode(2) target = 1e100
You return 1 instead of 2.
I wonder how many solutions would correctly handle
target = float('inf'). I suspect none. But that's a really mean case, and debatable whether it's valid.
@StefanPochmann yup, you are right, it's debatable, whatever I change it, you change the target to 1 googol, and I change the gap to 2 googol to conquer it -> dead loop
So Thought is right, and others can learn something from this solution, that is enough. :-)
@StefanPochmann if you choose target = 1e100, and your python solution will also return 1 instead of 2. So this is not the main problem. :-)
Ha, right. Not enough resolution to distinguish between 1 and 2 at that scale. I guess the easiest fix would be to limit target before we do anything else, like
target = max(min(target, 2**32), -2**32)
Edit: Actually it's easier to just break ties in favor of the deeper node's value.
Hmm, some of my solutions had unintentionally already solved that correctly. I now fixed the remaining ones as well, so that they solve very large targets, including infinity, correctly.
class Solution(object): def closestValue(self, root, value): gap = abs(root.val - value) ans = root while root is not None: if root.val == value: return root.val elif value < root.val: if abs(root.val - value) < gap: ans = root gap = abs(root.val - value) root = root.left else: if abs(root.val - value) < gap: ans = root gap = abs(root.val - value) root = root.right return ans.val
why not use root.val-val as inital value, which may not have bugs, stepahn : )
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.