通过给定总和找到根到叶路径。代码通过字符串成功，列表失败

Question

我正在看一个二进制树问题。目的是找到从根到叶的所有路径，以使路径上的值总和到给定的 k 。

为此，我以两种不同的方式编写了相同的算法：

1. 第一个版本使用字符串参数a。
2. 第二版使用列表参数a。

他们应该给出相同的路径结果，但是第二版将打印出几乎包含树中所有值的路径。

版本1

def rootToLeafPathsSumToK(root, k, a):
    if root == None :
        return None
    
    if root.left==None and root.right==None:
        if root.data==k:
            print(a+ str(root.data)+" ")
        return

    a+=str(root.data)+" "
    rootToLeafPathsSumToK(root.left,k-root.data,a)
    rootToLeafPathsSumToK(root.right,k-root.data,a)

输出：

5 6 2 
5 7 1 

版本2

def rootToLeafPathsSumToK(root, k, a):
    if root == None :
        return None
    
    if root.left==None and root.right==None:
        if root.data==k:
            a.append(root.data)
            print(a)
        return

    a.append(root.data)
    rootToLeafPathsSumToK(root.left,k-root.data,a)
    rootToLeafPathsSumToK(root.right,k-root.data,a)

Answer 1

这两个代码段之间的区别是：

• 在第一个版本中，其中a是字符串，您可以执行a+= str（root.data）+“” 。这将创建一个新的字符串并将其分配给本地变量a。此操作不会影响呼叫者作为参数传递的字符串。此外，字符串在Python中是不变的。

• 在第二版中，其中a是列表，您可以执行a.append（root.data）。此不会创建一个新列表。它突变了呼叫者作为参数通过的列表。实际上，该代码仅具有一个列表。因此

因此，在第一个版本中，添加值的效果是局部的，并且不会影响呼叫者的字符串，在第二版中，效果也可以到达呼叫者，因为它们使用了 same same list 。

要在第二个代码版本中应用相同的local 原理，请使用以下方式将调用替换为附加：

a = a + [root.data]

现在原始列表 a 未突变。而是创建了一个新列表，并将其分配回本地变量a。但是在这里，呼叫者的列表仍然是原始列表。现在创建了一个新列表。