Home Ask Login Register

Developers Planet

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

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):
class Solution(object):
    def pathSum(self, root, sum):
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        if not root:
            return res
        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:
        if root.left!=None:
        if root.right!=None:

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:
if root.right!=None:

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

Your original code passes in a new list each time:


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
if root.right!=None:
    temp+=[root.right.val] # the updated value could be used here, which is wrong 

Post Status

Asked in February 2016
Viewed 1,650 times
Voted 9
Answered 3 times


Leave an answer

Quote of the day: live life