I want to know whether my algorithm is correct
class Solution: # @param root, a tree node # @param sum, an integer # @return a list of lists of integers def __init__(self): self.solution =  def pathSum(self, root, sum, l=): if root is None: return  l.append(root.val) if root.left is None and root.right is None and root.val == sum: self.solution.append(l) if root.left is not None: self.pathSum(root.left, sum-root.val, l) if root.right is not None: self.pathSum(root.right, sum-root.val, l) return self.solution
1 2 2
Find sum of 3.
In python, when you pass a list in, changing it will change all instances of that list. The
l= in your function declaration does not change that. Therefore, every time you reach a leaf and the sum is correct, it will append
l. Unfortunately, using the same
l each time means that every instance of
l is changed with it, including all the lists in
solution. Since every node is added to
l is added to
solution each time you find a valid path, you will end up with k copies of all the nodes in the tree in a preorder traversal, where k is the number of valid paths.
I suggest using
list(l) as the final parameter, like so:
self.pathSum(root.left, sum-root.val, list(l))
This will make a copy of the list, so changes along other paths will not affect it.