Wie erhalte ich den Pfad von der Wurzel eines Binärbaums zu allen Blättern in 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)

Das ist mein Code, aber er druckt jedes Mal alle Knoten. Dann entdeckte DEBUG, dass das tmp-Array jedes Mal, wenn es zum rechten Teilbaum zurückkehrt, den Zustand des linken Teilbaums beibehält, bevor es ihn durchquert, was überhaupt nicht der Zustand von der Wurzel zum rechten Teilbaum ist.
Ist das ein Problem mit dem Umfang? Da ich aber keine Lösung finde, bitte ich hier um eine Antwort, danke

Answer 1

是作用域的问题，你的算法大概没有多少问题，主要是你要知道，给函数传参的时候，尤其是传入可变参数（你这里是列表）的时候，你要做到心中有数。这里你的问题主要集中在tmp上面，之所以会保留左子树的状态，是因为你在遍历左子树的时候，添加了左子树到tmp中了，然后你又在下一次递归调用中把添加后的列表放到了列表中，如果只有左子树，是没问题的，如果有右子树，就会出现问题。语言表达能力有限，我把改过的代码贴出来给你看看

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)