Python different recursive solutions.


  • 2
    C
    # 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))

  • 0

    For

        root = TreeNode(2)
        root.left = TreeNode(1)
        target = sys.maxint
    

    your third solution (the BST one) incorrectly returns sys.maxint.


  • 0

    Thanks, just added couple more test cases.


  • 0
    C

    Yes, you are correct, extra checking should be added. It can be fixed by adding: if not node:
    return root.val


  • 0

    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.


  • 0

    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.


Log in to reply
 

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