这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指向它。

对于第二种实现，您有一个single列表，该列表一直在传递。您应该在dfs返回之前弹出节点。

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"

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