Easy Understanding Python Iterative Solution


  • 0
    C
    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

  • 0

    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.


  • 0

    Thanks Stefan. I've just added your test cases.


  • 0
    C

    yeah, Thanks for this comment, I also came up with the same problem before I ran it, and I have fixed it right now.


  • 0
    This post is deleted!

  • 0

    Sorry, new counter-example :-)

    root = TreeNode(1500000000)
    root.left = TreeNode(1400000000)
    target = -1500000000
    

    Your current solution returns 1500000000.


  • 0
    R

    could you show fixed code? maybe maintain two pointer?


  • 0
    C

    the above code is already the fixed for the first problem, but second problem is pointed by stefan... coming soon...lol


  • 0
    C

    @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


  • 0
    C

    @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

  • 0

    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.


  • 0
    C

    @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. :-)


  • 0
    C

    @StefanPochmann if you choose target = 1e100, and your python solution will also return 1 instead of 2. So this is not the main problem. :-)


  • 0

    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.


  • 0

    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.


  • 0
    R
    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 : )


  • 0
    C

    nice modification, I have updated : )


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.