Your answer is one click away!

Runze Dong February 2016
### 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

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

Martijn Pieters February 2016

`+=`

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.

Austin Hastings February 2016

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]!
```

cricket_007 February 2016

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)
```

Asked in February 2016

Viewed 1,650 times

Voted 9

Answered 3 times

Viewed 1,650 times

Voted 9

Answered 3 times