切片得到神奇的更新 [英] Slice getting updated magically

问题描述

我正在尝试编写一个程序来查找二叉树中的所有根到叶路径，其中每个路径的和等于给定的和。

以下是我编写的代码

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呢？

我知道切片是通过值传递的，切片值是一个标头，用于描述后备数组的连续部分。但我仍然不明白该值是如何在随后的递归中被替换的。

推荐答案

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的切片将不会与任何人共享其基础数组。

这篇关于切片得到神奇的更新的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！