Comment obtenir le chemin de la racine d'un arbre binaire à toutes les feuilles en python ?

Question

'''这是二叉树的定义'''
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
'''这是路径函数'''
def dfs(node, result, tmp):
    if node == None:
        return 
    tmp.append(node)
    if node.left == None and node.right == None:
        result.append([i.val for i in tmp])
        return
    dfs(node.left, result, tmp)
    dfs(node.right, result, tmp)

C'est mon code, mais il imprime tous les nœuds à chaque fois. Ensuite, DEBUG a découvert que chaque fois qu'il revient vers le sous-arbre droit, le tableau tmp conservera l'état du sous-arbre gauche avant de le parcourir, ce qui n'est pas du tout l'état de la racine au sous-arbre droit.
Est-ce un problème de portée ? Mais je ne trouve pas comment le résoudre, alors je demande une réponse ici, merci

Answer 1

C'est une question de portée. Il n'y a probablement pas beaucoup de problèmes avec votre algorithme. L'essentiel est que vous devez le savoir lorsque passez des paramètres à une fonction, en particulier lorsque vous transmettez des paramètres variables (dans votre cas, c'est une liste). ), il faut le garder à l'esprit. Votre problème ici est principalement axé sur tmp. La raison pour laquelle l'état du sous-arbre gauche est conservé est que lorsque vous parcourez le sous-arbre gauche, vous ajoutez le sous-arbre gauche à tmp, puis vous effectuez le prochain appel récursif Mettez l'ajouté. list dans la liste. S'il n'y a qu'un sous-arbre de gauche, il n'y a pas de problème. S'il y a un sous-arbre de droite, il y aura un problème. Ma capacité d'expression linguistique est limitée, je publierai donc le code modifié pour que vous puissiez le voir

import copy


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None


def dfs(node, result, tmp=list()):
    if node is None:
        return

    tmp.append(node)
    # 这里需要用拷贝而不是用 = 赋值，也可以遍历赋值
    tmp1 = copy.deepcopy(tmp)

    if node.left is None and node.right is None:
        result.append([i.val for i in tmp])
        return

    if node.left is not None:
        dfs(node.left, result, tmp)
    # 遍历右子树需要带上不同的变量，否则左子树的tmp和右子树的tmp都指向一块内存
    if node.right is not None:
        dfs(node.right, result, tmp1)


if __name__ == '__main__':
    node1 = TreeNode('a')
    node2 = TreeNode('b')
    node3 = TreeNode('c')
    node4 = TreeNode('d')
    node5 = TreeNode('e')
    node6 = TreeNode('f')
    node7 = TreeNode('g')

    node1.left = node2
    node1.right = node3
    node2.left = node4
    node2.right = node5
    node4.left = node6
    node3.left = node7

    r = []
    dfs(node1, result=r)
    print(r)