[TLE] Does my algorithm works? (Python)


  • 0
    L

    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
    M
      1
    2   2
    

    Find sum of 3.
    returns [[1,2,2],[1,2,2]]

    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, and 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.


Log in to reply
 

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