LeetCode Path Sum II递归Go语言解法基础用例失败排查

你遇到的问题本质上是Go语言切片的引用类型特性导致的，和C里的容器（比如vector）行为差异很大——C的vector默认是值拷贝语义，而Go的切片传递的是切片结构体的拷贝，但底层数组是共享的，这就会引发意想不到的副作用。

第一种代码的问题点 #

来看你的第一段代码：

var answer[][]int
func hasPathSum(root *TreeNode, sum int, path []int){
    if root == nil {
        return
    }
    newPath := append(path, root.Val)
    sum = sum - root.Val
    if root.Left == nil && root.Right == nil && sum == 0 {
        answer = append(answer, newPath) // 直接将newPath加入answer
        fmt.Println(answer)
        return
    }
    if root.Left != nil {
        hasPathSum(root.Left, sum, newPath)
    }
    if root.Right != nil {
        hasPathSum(root.Right, sum, newPath)
    }
}

这里的关键问题是：newPath是基于path执行append得到的切片。如果path的底层数组还有剩余容量，append不会创建新数组，newPath和后续递归中生成的其他切片会共享同一个底层数组。

当你把newPath加入answer后，后续的递归调用（比如处理右子树时）可能会继续修改这个共享的底层数组，导致已经存在于answer中的newPath内容被意外覆盖，最终输出的结果自然不符合预期。

举个直观的例子：假设path的容量是5、长度是2，append后newPath长度变为3，但底层数组还是原来的。当后续递归继续往这个数组里加元素时，之前存入answer的newPath指向的数组元素就会被篡改。

第二种代码为什么能正常工作 #

再看你的第二段代码：

var answer[][]int
func hasPathSum(root *TreeNode, sum int, path []int){
    if root == nil {
        return
    }
    sum = sum - root.Val
    if root.Left == nil && root.Right == nil && sum == 0 {
        answer = append(answer, append(path, root.Val)) // 生成新切片再加入answer
        fmt.Println(answer)
        return
    }
    if root.Left != nil {
        hasPathSum(root.Left, sum, append(path, root.Val))
    }
    if root.Right != nil {
        hasPathSum(root.Right, sum, append(path, root.Val))
    }
}

这里的核心是：每次传递给递归函数、以及存入answer的，都是append(path, root.Val)生成的新切片。

当执行append(path, root.Val)时，如果原path的容量不足以容纳新元素，Go会分配全新的底层数组，把原元素拷贝过去再加入新值；即使容量足够，这个操作返回的是一个长度+1的切片结构体（后续如果有超过容量的append会触发扩容）。更关键的是，在叶子节点存入answer时，append(path, root.Val)相当于对当前路径做了一次“快照”，确保存入answer的切片内容不会被后续递归操作修改。

简单说，第二种写法通过每次隐式生成新切片，避开了共享底层数组的坑。

修正第一种代码的方法 #

如果你想保留第一种代码的结构，只需要在将newPath加入answer时，主动复制一份切片内容，而不是直接引用原切片：

if root.Left == nil && root.Right == nil && sum == 0 {
    // 把newPath的元素全部拷贝到新切片中，再加入answer
    answer = append(answer, append([]int{}, newPath...))
    fmt.Println(answer)
    return
}

这里append([]int{}, newPath...)会创建一个全新的底层数组，将newPath的元素全部复制进去，后续递归操作就不会影响已经存入answer的路径了。

为什么C++的类似写法没问题 #

C中的vector是值类型，传递vector或者执行push_back时默认会做值拷贝（除非你显式传递引用）。所以在C中，每次递归传递的路径都是当前路径的副本，后续修改不会影响之前保存的路径，自然不会出现这个问题。这是Go切片的引用语义和C++容器的值语义的核心区别。

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