My python code lTE. Is there someone can told me how to let it more efficient


  • 0
    D

    Below is my code.

    class Solution:
        def pathSum(self, root, sum):
            paths = []
            if root == None:
                return []
            stack = [(root,[root.val], sum)]
            while len(stack):
                node, path, lSum = stack.pop()
                path.append(node.val)
    
                if node.left == None and node.right == None:
                    if lSum == node.val:
                        paths.append(path)
                    continue
                        
                if node.left != None:
                    stack.append((node.left, path, lSum-node.val))
                if node.right != None:
                    stack.append((node.right, path, lSum-node.val))
            # print "len of path :" + str(len(path)) 
            return paths

  • 0
    H

    Your code doesn't give the correct answer. The path variable that is associated with each node and pushed into the stack always refers to the same list object, therefore whenever a node is appended, path associated with every node would grow. Finally you get a number of (maybe zero) copies of the same list. Some readings on how Python passes arguments should be very helpful.


  • 0
    D

    sorry i pasting the wrong answer.below is my code.
    class Solution:
    # @param root, a tree node
    # @param sum, an integer
    # @return a boolean
    def pathSum(self, root, sum):
    result = []
    stack = []
    if root == None:
    return result

        stack.append((root, []))
    
        while stack != []:
            node, l = stack.pop()
            l.append(node.val)
    
            if node.left == None and node.right == None:
                lSum = 0
                # print l
                for x in l:
                    lSum += x
                # print "lSum : " +  str(lSum)
                if lSum == sum:
                    result.append(l)
            else:
                if node.left != None:
                    stack.append((node.left, l[:]))
                if node.right != None:
                    stack.append((node.right, l[:]))
        return result

Log in to reply
 

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