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

Answers


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)

Post Status

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

Search




Leave an answer


Quote of the day: live life