Python 中的二叉树路径总和

Question

问题是二叉树，我需要打印总和为目标数的路径。在 google 的帮助下，我的逻辑是正确的。但是我看不懂一行代码。

代码：

class Node:
    
    def __init__(self,data):
        
        self.data = data
        self.left = None
        self.right = None
        
class Tree:
    
    def __init__(self,root):
        self.root = Node(root)


def findPaths(root,tot):
    
    if root is None:
        return None
    
    all_paths = []
    
    findPathsRecur(root,tot,[],all_paths)
    
    return all_paths


def findPathsRecur(node,tot,currPath,all_paths):
    
    #global all_paths
    
    if node is None:
        return None
    
    #Append node to current path
    
    currPath.append(node.data)
    
    
    if node.data == tot and (node.left is None and node.right is None):
       
        all_paths.append(list(currPath)) #=> This is where I have trouble
        
        
    else:
        
        findPathsRecur(node.left,tot-node.data,currPath,all_paths)
        findPathsRecur(node.right, tot-node.data,currPath,all_paths)
        
    del currPath[-1]
    
    return all_paths

在上面的代码中，只有当我将 currPath 投射到一个列表中时，我才会得到正确的输出，否则我得到的只是一个空列表。我尝试使用 type() 函数进行调试，即使 returns currPath 的类型仅作为列表。有什么必要或为什么要使用 list(currPath)。请在下面找到输出。

Output while using `all_paths.append(list(currPath))`:

[[1, 7, 4], [1, 9, 2]]

Output while using `all_paths.append(currPath)`:

[[], []]

Answer 1

它的发生是因为 all_paths.append(currPath)，currPath 被作为指针传递，但是当你使用 list(currPath) 时，你基本上是将它的副本添加到 all_paths。要确认这一点，您可以尝试：all_paths.append(currPath.copy())，它会给您正确的输出。

当您将 list1 附加到另一个 list2 时，您基本上是将 list1 的引用附加到 list2。如果 list1 在其他任何地方被修改，它也会反映在 list2 上。确认这一点：

a = []
a.append(1)
a.append(2)
b = []
b.append(a)
print (b)  #   OUTPUT: [[1, 2]]
del a[0]
print (b)  #   OUTPUT: [[2]]

Python 中的二叉树路径总和

Binary Tree Path Sum in Python

python

binary-tree