为什么 dfs 的这两种实现会给出不同的结果？

Question

这个给出了正确的结果：

def binaryTree(root):
    paths = []

    def dfs(root, path=""):
        if root:
            if path != "":
                path += "->"
            path += str(root.val)
            if not root.left and not root.right:
                paths.append(path)
            dfs(root.left, path)
            dfs(root.right, path)

    dfs(root)
    return paths # gives ['1->2->4', '1->2->5', '1->3']

在这一个路径列表不断增长：

def binaryTree2(root):
    paths = []

    def dfs(root, path=[]):
        if root:
            path.append(root.val)
            if not root.left and not root.right:
                paths.append("->".join(map(str, path)))
            dfs(root.left, path)
            dfs(root.right, path)

    dfs(root)
    return paths # gives ['1->2->4', '1->2->4->5', '1->2->4->5->3']

树是这样的：<1, <2, <4, None, None>, <5, None, None>>, <3, None, None>>

唯一的区别是，在一个中我连接字符串，在另一个中我追加到列表。

Answer 1

所以在第一个实现中：所有 path += ... 语句本质上都是创建一个新字符串并让 path 指向它。

至于第二个实现，您有一个一直传递的单个列表。您应该在 dfs returns.

之前弹出节点

def binaryTree2(root):
    paths = []

    def dfs(root, path=[]):
        if root:
            path.append(root.val)
            if not root.left and not root.right:
                paths.append("->".join(map(str, path)))
            dfs(root.left, path)
            dfs(root.right, path)
            path.pop() # this clears your stack as your functions return

    dfs(root)
    return paths

编辑：Python 字符串是不可变的 - 即一旦创建，便无法修改。

# below line essentially creates a pointer,
# and a string object that `path` points to.
path = "huhu"

# this creates another string object `huhu123`.
# So at this point we have 3 strings objects,
# "123", "huhu" and "huhu123". And a pointer `path` if you will.
# `path` points to "huhu123"
path += "123"

如果我们有更多无辜的对象而不是字符串，一旦它们没有引用，它们就会被垃圾收集。字符串得到特殊处理，在我们的例子中，所有 3 个都是 interned.

为什么 dfs 的这两种实现会给出不同的结果？

How come these 2 implementations of dfs give different results?

python

depth-first-search