返回二叉树中叶节点的列表路径

eaf3rand  于 2021-08-20  发布在  Java
关注(0)|答案(1)|浏览(312)

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

4
   / \
  9   0
 / \
1   5

此列表的预期输出为: [[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

quhf5bfb

quhf5bfb1#

提示是将相同的列表传递给递归调用,然后向其中添加值。正如有人曾经说过的,“共享可变状态是所有邪恶的根源”(或类似的东西)。
当前_路径示例化一次,每个节点都会在执行时添加自身。然后,当它命中一个节点时,它会将一个指向当前路径的指针添加到解决方案路径列表中——因此它们每个都会向同一个列表添加一个指针。
用类似的方法解决问题-

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

相关问题