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