递归函数传入字符串与数组参数的差异解析（LeetCode场景）

这是LeetCode中二叉树的所有路径问题，要求返回根节点到所有叶子节点的路径，路径以"->"连接的字符串数组形式返回（示例：["1->2->5", "1->3"]）。以下两个代码实现均能解决该问题，核心疑问的答案正是你猜想的：字符串是不可变对象，传递时生成副本；数组是可变对象，传递的是引用，修改会影响原对象。

字符串实现解法 #

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []

        def dfs(node, currPath):
            if not node:
                return
            
            currPath += str(node.val)
            if not node.right and not node.left:
                res.append(currPath)
                return
            
            dfs(node.left, currPath + "->")
            dfs(node.right, currPath + "->")
        
        dfs(root, "")
        return res

数组实现解法 #

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []

        def dfs(node, currPath):
            if not node:
                return
            
            currPath.append(str(node.val))
            if not node.right and not node.left:
                res.append("->".join(currPath))
            
            dfs(node.left, currPath)
            dfs(node.right, currPath)
            currPath.pop()
        
        dfs(root, [])
        return res

差异原因详解 #

字符串解法：不可变对象的独立副本 #

Python中的字符串是不可变对象，任何对字符串的修改操作（比如+=、拼接）都会生成一个全新的字符串副本，而非修改原字符串：

• 执行currPath += str(node.val)时，会基于原currPath创建新字符串，原字符串不受影响；
• 递归调用dfs(node.left, currPath + "->")时，传递的是拼接后的新字符串，左子树递归中对路径的修改完全独立于当前层和右子树的路径；
• 当递归到叶子节点时，将当前的路径副本加入结果后直接return，不会影响上层递归的currPath——因为上层的currPath是另一个独立的字符串，后续右子树递归用的也是上层自己生成的新字符串副本，和叶子节点的路径没有关联。

数组解法：可变对象的共享引用 #

数组（列表）是可变对象，递归传递的是数组的内存引用，所有递归层操作的都是同一个数组对象：

• 执行currPath.append(str(node.val))时，直接修改的是这个共享的数组；
• 如果递归到叶子节点后直接return，不执行currPath.pop()，当前节点的值会一直留在数组中。后续处理上层的右子树分支时，数组里会包含之前叶子节点的元素，导致生成错误的路径；
• 必须在左右子树递归完成后执行currPath.pop()，把当前节点从数组中移除，恢复到进入当前递归层之前的状态，保证后续分支的路径是纯净的。

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