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 was like this.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
# 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.

1 2 3 4 5 |
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

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

Finally, I got the correct answer.