Trick on Appending a List to Another List in Python

Today I spent some time on practicing coding. When I was trying to solve a problem about finding paths with elements whose sum equals to a specified value, given a binary tree and a value, I stumble against some unknown problems. 

As I firstly finished my code, I got a null result. My codes at beginning are like this. 

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def FindPath(self, root, expectNumber):
        if not root:
            return []
        res = list()
        path = list()
                    
        def SubFind(root, path, expectNumber):
            path.append(root.val)
        
            # if root is leaf
            if not root.left and not root.right and expectNumber == root.val:
                res.append(path)
        
            # if root is not leaf
            if root.left:
                SubFind(root.left, path, expectNumber - root.val)
            if root.right:
                SubFind(root.right, path, expectNumber - root.val)
            path.pop()

        SubFind(root, [], expectNumber)
        return res

 

Can you guys find where the problem lies?

Actually, the problem happens when I was trying to append a path to the res list followed by pop operation. You may better understand with the example below. 

a, b = [], [123]
a.append(b)
print('Before pop:', a)
b.pop()
print('After pop:', a)

I bet now you must realize the appending here is about passing by reference. What is appended to the list a is just a reference of list b. When you modify the b, the corresponding content in a will also change. 

In this way, I have to reassign another list and copy the content from b to this list. That is

path_cp = [i for i in path]
res.append(path_cp)

Finally, I got the correct answer. 

Leave a Reply

Your email address will not be published. Required fields are marked *