Python二叉树遍历结果异常：字符串与列表传参差异求助

你的问题核心在于Python中字符串是不可变类型，而列表是可变类型，这直接导致了两者在递归传递时的行为差异，我给你拆解清楚：

1. 字符串的正确行为解析 #

在你的代码里，path += str(root.val) 这行看起来是修改了path，但实际上因为字符串不可变，这行代码会创建一个全新的字符串对象，并把新对象的引用赋值给当前作用域的path变量。

每次递归调用trav时，传递的都是这个新字符串的引用——也就是说，每个递归分支的path都是独立的，不会和其他分支互相干扰。当你到达叶子节点时，path刚好是当前路径的字符拼接，'->'.join(path) 会把每个字符用->连接，刚好得到正确的路径字符串。

2. 列表的错误原因：引用传递与可变对象 #

而列表temp的情况完全不同：

• temp.append(root.val) 是直接在原列表对象上修改，因为列表是可变类型。
• 你在第一次调用trav时传入的是同一个temp列表的引用，所有递归分支共享这个列表对象。当递归深入左子树时，你往temp里加了节点值；递归回溯后再走右子树时，temp里已经包含了左子树的节点值，没有被清除，最终所有路径的节点都会累积到temp里，导致self.path_temp的结果错误。

你问“Python中的列表是否在内存中具有持久性”，更准确的说法是：列表作为可变对象，在内存中是一个持续存在的实体，所有持有该对象引用的地方，看到的都是同一个对象的状态。修改操作会直接改变这个实体的内容，而不是创建新对象。

3. 修正列表版本的两种方案 #

要让path_temp得到正确结果，有两种常用思路：

方案一：回溯法（推荐，内存效率更高） #

在递归调用后，撤销对temp的修改，把当前添加的节点值移除：

def binaryTreePaths(self, root: TreeNode) -> List[str]:
    self.path = []
    temp = []
    self.path_temp = []
    def trav(root, path, temp):
        if root:
            path += str(root.val)
            temp.append(root.val)
            if root.right is None and root.left is None:
                self.path.append('->'.join(path))
                # 注意这里要把temp里的数字转成字符串再join
                self.path_temp.append('->'.join(map(str, temp)))
            trav(root.left, path, temp)
            trav(root.right, path, temp)
            temp.pop()  # 回溯：移除当前节点，恢复temp的状态
    trav(root, '', temp)
    print(self.path)
    print(self.path_temp)

方案二：传递列表副本 #

每次递归时，创建一个新的列表副本传递进去，这样每个分支都用自己独立的列表：

def binaryTreePaths(self, root: TreeNode) -> List[str]:
    self.path = []
    temp = []
    self.path_temp = []
    def trav(root, path, temp):
        if root:
            new_path = path + str(root.val)
            # 创建新列表，包含原temp的所有元素加上当前节点值
            new_temp = temp + [root.val]
            if root.right is None and root.left is None:
                self.path.append('->'.join(new_path))
                self.path_temp.append('->'.join(map(str, new_temp)))
            trav(root.left, new_path, new_temp)
            trav(root.right, new_path, new_temp)
    trav(root, '', temp)
    print(self.path)
    print(self.path_temp)

最后再总结一下关键区别 #

• 不可变类型（字符串、整数、元组）：任何“修改”操作都会生成新对象，原对象保持不变，传递时不会出现跨分支的干扰。
• 可变类型（列表、字典、集合）：修改操作直接作用于原对象，传递的是对象引用，所有共享该引用的地方都会看到修改结果。

内容的提问来源于stack exchange，提问作者pat