I am getting a different result when I am using append(path) vs. append(list(path))
I have the following code to find all paths for a sum:
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def find_paths(root, sum):
allPaths = []
dfs(root, sum, [], allPaths)
return allPaths
def dfs(root, sum, path, res):
if not root:
return
path.append(root.val)
if root.val == sum and root.left is None and root.left is None:
res.append(path)
dfs(root.left, sum - root.val, path, res)
dfs(root.right, sum - root.val, path, res)
del path[-1]
def main():
root = TreeNode(12)
root.left = TreeNode(7)
root.right = TreeNode(1)
root.left.left = TreeNode(4)
root.right.left = TreeNode(10)
root.right.right = TreeNode(5)
sum = 23
print("Tree paths with sum " + str(sum) +
": " + str(find_paths(root, sum)))
main()
This has the following output:
Tree paths with sum 23: [[], []]
But if I change the res.append(path) to res.append(list(path)) which will then return the correct answer Tree paths with sum 23: [[12, 7, 4], [12, 1, 10]]. I am confused on why using the list operation would change the answer.
>Solution :
res.append(path) appends the object path itself to the list res. After that line, when you modify the path object (like del path[-1]), the modification is also applied to the appended object in res, because, well, they are the same object.
list(path), on the other hand, "copies" the path. So this one is now a different object from path. When you modify path after that, the modification does not propagates to this different object.
You will have the same result if you do path[:] or path.copy() instead of list(path).