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)

這是我的程式碼，但是每次都是列印全部節點。然後DEBUG發現，每次遞歸到右子樹，tmp數組會保留之前遍歷完左子樹的狀態，而根本不是我想的從根到右子樹的狀態。
這是作用域的問題？可我找不到怎麼解決，在此請求解答，謝謝

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)