Python recursive solution


  • 1
    G
    # Definition for a  binary tree node
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        # @param root, a tree node
        # @param sum, an integer
        # @return a list of lists of integers
        # 2:32
        def pathSum(self, root, sum):
            output = []
            self.findPathSum(root, sum, [], output)
    
            return output
    
        def findPathSum(self, root, sum, temp, output):
            if not root:
                return
    
            if not root.left and not root.right and sum == root.val:
                temp.append(root.val)
                output.append(temp[:])
                return
    
            sum -= root.val
            temp.append(root.val)
            self.findPathSum(root.left, sum, temp[:], output)
            self.findPathSum(root.right, sum, temp[:], output)

  • 0
    Q

    great solution!
    however, I find something hard to explain, if I replace temp[:] to temp in your code( it is the same right? ), I get the TLE error, could you please tell me the difference?


  • 0
    G

    temp is just a reference, whereas temp[:] is a shallow copy of the temp array. When you are doing recursive call, you want to lock the current state of the temp array, otherwise when you are changing the temp in the left tree, you will also change the value of temp in the right subtree


Log in to reply
 

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