Bagaimana untuk mendapatkan laluan dari akar pokok binari ke semua daun dalam 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)

Ini adalah kod saya, tetapi ia mencetak semua nod setiap kali. Kemudian DEBUG mendapati bahawa setiap kali ia berulang ke subpokok kanan, tatasusunan tmp akan mengekalkan keadaan subpokok kiri sebelum melintasinya, yang bukan keadaan dari akar ke subpokok kanan sama sekali.
Adakah ini isu skop? Tetapi saya tidak dapat mencari cara untuk menyelesaikannya, jadi saya meminta jawapan di sini, terima kasih

Answer 1

Ini masalah skop mungkin tidak banyak masalah dengan algoritma anda Perkara utama ialah anda perlu tahu bahawa apabila melalui parameter ke fungsi, terutamanya apabila menghantar parameter berubah (dalam kes anda, ia adalah senarai. ), anda perlu ingat tak terkira. Masalah anda di sini tertumpu terutamanya pada tmp Sebab mengapa keadaan subpokok kiri dikekalkan adalah kerana apabila anda melintasi subpokok kiri, anda menambah subpokok kiri pada tmp, dan kemudian anda membuat panggilan rekursif seterusnya Letakkan tambah. senaraikan ke dalam senarai Jika hanya terdapat subtree kiri, tiada masalah. Keupayaan ekspresi bahasa saya adalah terhad, jadi saya akan menyiarkan kod yang diubah suai untuk anda lihat

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)