Python recursive solution

  • 1
    # 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:
            if not root.left and not root.right and sum == root.val:
            sum -= root.val
            self.findPathSum(root.left, sum, temp[:], output)
            self.findPathSum(root.right, sum, temp[:], output)

  • 0

    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

    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.