切片神奇地更新

Question

我正在尝试编写一个程序来查找二叉树中的所有 root-to-leaf 路径，其中每条路径的总和等于给定的总和。

以下是我想出的代码

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？

我知道切片是按值传递的，切片值是 header，描述了支持数组的连续部分。但是我仍然不明白在随后的递归中该值是如何被替换的。

Answer 1

Go 中的切片是包含指向底层数组的指针、长度和容量的小型描述符。有关详细信息，请参阅 Slice internals。

将切片传递给函数时，会复制描述符但不会复制底层数组。这意味着 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中的切片共享。但是节点 7 现在将 7 附加到长度为 3 的切片，覆盖了底层数组中 2 的先前值。

一个快速的解决方案是将 currentPath 的内容复制到 path 而不是直接存储切片：

    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
    }

重要说明：当切片需要增长时，底层数组被复制，产生一个单独的数组。在该示例中，切片在节点 4 处增长到容量 4，因此它在节点 2 和 7 处保持相同的底层数组。如果它在节点 2 生长，添加到 path 的切片将不会与任何人共享其底层数组。

切片神奇地更新

Slice getting updated magically

algorithm

binary-tree

go

slice