Блог

Вопрос в двоичном дереве, мне нужно напечатать пути, которые суммируются с целевым числом. Я правильно понял логику с помощью 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 (), даже если она возвращает тип пути только в виде списка. В чем необходимость или почему я должен использовать список(currPath). Пожалуйста, ознакомьтесь с результатами ниже.

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

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

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

[[], []]
 

Это происходит потому , что with all_paths.append(currPath) currPath передается как указатель, но при использовании list(currPath) вы в основном добавляете его копию all_paths . Чтобы подтвердить это, вы можете попробовать: all_paths.append(currPath.copy()) , это даст вам правильный вывод.

Когда вы добавляете список 1 в другой список 2, вы в основном добавляете ссылку на список 1 в список 2. Если список 1 будет изменен в другом месте, это отразится и на списке 2. Чтобы подтвердить это:

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