algorithm - slice 神奇地更新

Question

我正在尝试编写一个程序来查找二叉树中所有从根到叶的路径，其中每个路径的总和等于给定的总和。
以下是我想出的代码

package main

import (
    "fmt"
)

type TreeNode struct {
     Val int
     Left *TreeNode
     Right *TreeNode
}

func main() {
    root := TreeNode{
       Val : 5,
       Left: &TreeNode { 
           Val : 4,
           Left : &TreeNode {
                Val : 11,
                Left : &TreeNode { Val : 2},
                Right : &TreeNode { Val : 7},
            
            },
        
        },
    }
    
    paths := [][]int{}
    pathSumRecursive(&root, 22, []int{}, &paths)
    fmt.Println("paths:", paths)
}


func pathSumRecursive(root *TreeNode, sum int, currentPath []int, paths *[][]int) {
    if root == nil {
        return 
    }
    
    currentPath = append(currentPath, root.Val)
    
    if root.Left == nil && root.Right == nil && root.Val == sum {
        *paths = append(*paths, currentPath)
        fmt.Println("paths updated ", *paths)
        return
    } 
    
    pathSumRecursive(root.Left, sum-root.Val, currentPath, paths) 
    pathSumRecursive(root.Right, sum-root.Val, currentPath, paths)
    
}

该程序的输出是

paths updated  [[5 4 11 2]]
paths: [[5 4 11 7]]

Play ground Link
我不明白的是，附加到paths的值是[5 4 11 2]，并且仅更新了一次。那么，是什么导致2(最后一个元素)更新为7呢？
我知道 slice 是按值传递的，而 slice 值是标题，它描述了后备数组的连续部分。但是我仍然不明白在随后的递归中如何替换该值。

Answer 1

Go中的slice是小的描述符，包含指向底层数组的指针，长度和容量。有关更多详细信息，请参见Slice internals。
当将 slice 传递给函数时，将复制描述符，但不会复制基础数组。这意味着currentPath将始终指向相同的基础数组，但通过递归将具有各种值:

节点11上的

:currentPath = [5 4 11]

节点2上的

:currentPath = [5 4 11 2]。添加到长度为4的paths中。

备份到节点11:currentPath = [5 4 11]

节点7上的

:currentPath = [5 4 2 7]。

在节点7中，基础数组仍然相同，并与paths中存储的 slice 共享。但是节点7现在将7附加到长度为3的 slice 上，覆盖了基础数组中2的先前值。
一种快速的解决方案是将currentPath的内容复制到path中，而不是直接存储 slice :

    if root.Left == nil && root.Right == nil && root.Val == sum {
        newSlice := make([]int, len(currentPath))
        copy(newSlice, currentPath)
        *paths = append(*paths, newSlice)
        fmt.Println("paths updated ", *paths)
        return
    }

重要说明:当 slice 需要增长时，将复制基础数组，从而得到单独的数组。在该示例中， slice 在节点4处增长到4的容量，因此它在节点2和7处保持相同的基础数组。如果在节点2处增长，则添加到path的 slice 将不会与任何人共享其基础数组。