Return 列出二叉树中叶节点的路径

Question

我正在编写一个 returns 到叶节点的所有路径的 dfs 函数。

此列表的预期输出为：[[4,9,5],[4,9,1],[4,0]]

这是我目前拥有的：

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


    def leafNodePaths(self, root):
        paths = []
        self.dfs(root, [], paths)
        print(paths)
        
    def dfs(self, root, current_path, paths): 
        if not root: 
            return
        
        current_path.append(root.val)
        if not root.left and not root.right:
            paths.append(current_path)
        else:
            self.dfs(root.left, current_path, paths)
            self.dfs(root.right, current_path, paths)

我得到的结果是 [[4, 9, 5, 1, 0], [4, 9, 5, 1, 0], [4, 9, 5, 1, 0]] 如何保持 current_path

的准确计数

Answer 1

提示是您将相同的列表传递给递归调用，然后向其添加值。正如有人曾经说过的那样，“共享可变状态是万恶之源”（或类似的话）。

current_path 被实例化一次，并且每个节点都将自己添加到它。然后，当它遇到一个节点时，它会将指向当前路径的指针添加到解决方案路径列表中 - 因此它们每个都会添加一个指向相同列表的指针。

按照以下方式解决问题-

current_path = copy(current_path) + [root.val]

Return 列出二叉树中叶节点的路径

Return list paths to leaf nodes in a binary tree

python

recursion

depth-first-search