Python dfs + recursive, interesting float to int issues


  • 0
    W

    I'm trying to work on a simple solution by first creating the possible paths and calculate them later. Here's my code.

    def sumNumbers(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if not root:
                return 0
            paths = []
            self.dfs(root, 0, paths, [(root, 0)])
            sums = 0
            for path in paths:
                height = path[-1][1] * (-1)
                pathSum = 0
                for node, depth in path:
                    pathSum += node.val * 10**(depth + height)
                sums += int(pathSum)
            return sums
            
        def dfs(self,node, depth, paths, path):
            if node:
                self.dfs(node.left, depth -1, paths, path+[(node.left, depth-1)])
                self.dfs(node.right, depth -1, paths, path+[(node.right, depth-1)])
                if not node.left and not node.right:
                    paths.append(path)
                    path = path[:-2]
                    return
    

    In here I noticed that Python int is not exactly transferring from float to integer.

    In the first version, I did something like this:

     height = path[-1][1] * (-1)
                pathSum = 0
                for node, depth in path:
                    pathSum += node.val * 10**depth
                pathSum = pathSum * 10 ** height
                sums += int(pathSum)
    

    This did not pass for a tree of two paths, 46505 and 449 because the pathSum variable, although appears to be 46505.0, when transferred to int, becomes 46504. Then I tried using math.ceil, and it gives error immediately on two paths 01 and 03, transferring 03 into 4.
    Perhaps this is related to floating number storage in computers and therefore could not be transferred exactly? Could anyone give a brief explanation.


Log in to reply
 

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