CODEWITHSUNDEEP
pythonrecursion
Runze Dong
Runze Dong

Reputation: 33

what's difference between these two statements about passing variables in Python recursively

I'm a new python learner. and there is a question confusing me a lot cause it really waste much time to think about.

There is a algorithm puzzle about binary tree, and a sum, you should find all root-to-leaf paths where each path's sum equals the given sum.

For example: Given the below binary tree and sum = 22

An example picture here

I have written a python recursive method like blew and it runs correctly on online judgment.

#definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val=x
        self.left=None
        self.right=None
class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        res=[]
        if not root:
            return res
        temp=[root.val]
        self.helper(root,sum,res,temp)
        return res
    def helper(self, root, sum, res, temp):
        if not root:
            return 0
        if root.left==None and root.right==None and sum==root.val:
            res.append(temp)
        if root.left!=None:
            self.helper(root.left,sum-root.val,res,temp+[root.left.val])
        if root.right!=None:
            self.helper(root.right,sum-root.val,res,temp+[root.right.val])

in the last four lines, I invoke the helper function recursively to find the path sum by pass root left child and root right child.

However, if i rewrite the code like below, I mean only last four lines

if root.left!=None:
    temp+=[root.left.val]
    self.helper(root.left,sum-root.val,res,temp)
if root.right!=None:
    temp+=[root.right.val]
    self.helper(root.right,sum-root.val,res,temp)

it gives me wrong answer and can't pass the online judgment.

Dose anyone know what is the difference between this two kind of ways in pass the parameter to a function in python. or it's any declare and pass problem in my code.

In my view, I can't see any difference. Thanks everyone.help me !

Upvotes: 0

Views: 63

Answers (3)

OneCricketeer
OneCricketeer

Reputation: 191854

The second version is incorrect because you would be updating the temp variable between the left leaf check and the right leaf check 

if root.left!=None:
    temp+=[root.left.val] # temp updated here
    self.helper(root.left,sum-root.val,res,temp)
if root.right!=None:
    temp+=[root.right.val] # the updated value could be used here, which is wrong 
    self.helper(root.right,sum-root.val,res,temp)

Upvotes: 0

aghast
aghast

Reputation: 15310

When you say temp += ... you are modifying temp. But you use it in both the left and right cases.

So you have:

temp = [0]
if root.left is not None:
    temp += [1]               # Now temp is [0, 1], probably okay
    ...
if root.right is not None:
    temp += [2]               # Now temp is [0, 1, 2], not [0, 2]!

Upvotes: 0

Martijn Pieters
Martijn Pieters

Reputation: 1123520

+= alters a list in-place:

>>> def inplace(l):
...     l += ['spam']
...
>>> def new_list(l):
...     l = l + ['spam']
...
>>> a = ['foo']
>>> inplace(a)
>>> a
['foo', 'spam']
>>> a = ['foo']
>>> new_list(a)
>>> a
['foo']

Your original code passes in a new list each time:

self.helper(root.left,sum-root.val,res,temp+[root.left.val])

but your altered code shares temp across all recursive calls and extends it each time. This matters because by creating a new list you gave the recursive calls for the left branch a new, independent list from the right branch of your recursion. By extending the list with += you now give a larger list to the right branch after processing the left branch.

Upvotes: 1

Related Questions