go - LeetCode问题路径总和II : Recursive solution bug

Question

我已经为golang中的question提交了以下解决方案，但对于基本情况失败了。我无法弄清楚为什么它失败了。

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)
        fmt.Println(answer)
        return
    }
    if root.Left != nil {
        hasPathSum(root.Left, sum, newPath)
    }
    if root.Right != nil {
        hasPathSum(root.Right, sum, newPath)
    }
    
}

func pathSum(root *TreeNode, sum int) [][]int {
    
    var path []int
    answer = [][]int{}
    hasPathSum(root, sum, path)
    return 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))
        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))
    }
    
}

func pathSum(root *TreeNode, sum int) [][]int {
    
    var path []int
    answer = [][]int{}
    hasPathSum(root, sum, path)
    return answer
}

我无法弄清楚两种解决方案之间的区别是什么。从递归的角度来看，这两种解决方案是相同的。此外，C++中的 similar solution通过所有检查。

Answer 1

发生问题是因为 slice 引用了基础数组，并且如果有空间，append不会重新分配新数组。参见https://blog.golang.org/slices-intro
这意味着当您使用append(path, root.Val)时，新 slice 有时会与path共享后备数组。这可能是个问题，例如:

if root.Left != nil {
    hasPathSum(root.Left, sum, append(path, root.Val))
}
if root.Right != nil {
    hasPathSum(root.Right, sum, append(path, root.Val))
}

在这里，两个分支都可能使用相同的支持数组。这是一个问题，因为在执行第一个 hasPathSum时，它可能会向 answer添加一个 slice ，但是该 slice 的基础数组仍可能在第二次调用 hasPathSum时使用，这将更改其内容。
这两个版本的代码都存在相同的问题，但是由于第二个版本不太可能引起问题，因为如果 append(path, root.Val)需要重新分配，那么您会在 hasPathSum的两个分支中获得两个不同的副本。这意味着该错误将以较低的频率发生。