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