我正在嘗試編寫一個程序來查找二叉樹中的所有從根到葉的路徑，其中每個路徑的總和等于給定的總和。以下是我想出的代碼package mainimport ( "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]]我不明白的是附加的值，paths它只[5 4 11 2]更新了一次。那么是什么導(dǎo)致2（最后一個元素）更新為7？我知道切片是按值傳遞的，切片值是標題，描述了支持數(shù)組的連續(xù)部分。但是我仍然不明白該值是如何在隨后的遞歸中被替換的。
1 回答
偶然的你
TA貢獻1841條經(jīng)驗 獲得超3個贊
Go 中的切片是包含指向底層數(shù)組的指針、長度和容量的小描述符。有關(guān)更多詳細信息，請參閱切片內(nèi)部。
將切片傳遞給函數(shù)時，會復(fù)制描述符，但不會復(fù)制底層數(shù)組。這意味著currentPath它將始終指向相同的底層數(shù)組，但通過遞歸將具有不同的值：
在節(jié)點
11：currentPath = [5 4 11]在節(jié)點
2：currentPath = [5 4 11 2]。添加到paths長度 4。備份到節(jié)點
11：currentPath = [5 4 11]在節(jié)點
7：currentPath = [5 4 2 7]。
在 node7中，底層數(shù)組仍然是相同的，并且與存儲在paths. 但是節(jié)點 7 現(xiàn)在附加7到長度為 3 的切片上，覆蓋了2底層數(shù)組中的先前值。
一個快速的解決方案是復(fù)制currentPathinto的內(nèi)容，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
}
重要說明：當(dāng)切片需要增長時，會復(fù)制底層數(shù)組，從而產(chǎn)生一個單獨的數(shù)組。在示例中，切片在節(jié)點處增長到 4 的容量，因此它在節(jié)點和4處保持相同的底層數(shù)組。如果它在 node 增長，添加到的切片不會與任何人共享其底層數(shù)組。272path
- 1 回答
- 0 關(guān)注
- 143 瀏覽
添加回答
舉報
0/150
提交
取消