Go slice的一个坑
问题
最近在刷leedcode，求二叉树的路径和，给定一个二叉树，求所有符合条件的路径。原题见 113. Path Sum II
这道题需要遍历所有的节点，并且记录遍历路径上的节点，可以使用回溯法，深度优先的方法。
不过最近用习惯了广度优先的方法，把二叉树变成一个有序的队列，这种思想很好玩，把多个选择的，需要遍历的变成一个有序的来进行遍历即可，就是一个万能模板。
下面贴下代码
var result [][]int
var ch = make(chan *TreeNode, 100)
var sumChan = make(chan int, 100)
var nodes = make(chan []int, 100)
for len(ch) > 0 {
for i := 0; i < len(ch); i++ {
//获取当前节点
cur := <-ch
//获取父节点的总和
parentSum := <-sumChan
//获取父节点的所有路径节点序列
parents := <-nodes
//当前节点的总和
curSum := parentSum + cur.Val
//当前节点的序列
curNodes := append(parents, cur.Val)
if cur.Left == nil && cur.Right == nil {
if curSum == targetSum {
// 添加当前节点序列到结果集
result = append(result, curNodes)
}
} else {
if cur.Left != nil {
ch <- cur.Left
sumChan <- cur.Val + parentSum
nodes <- curNodes
}
if cur.Right != nil {
ch <- cur.Right
sumChan <- cur.Val + parentSum
nodes <- curNodes
}
}
}
}
大家细读一下，不知道有没有看出来哪里不对，我先贴一下结果
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
上面这段代码的输出 Output: [[5,4,11,2],[5,8,4,1]]
why ？
可以看到，问题出在了最后一个右侧的子树和节点，看代码怎么看都没有错，为啥5 变成 1 了，肯定是哪里有引用了，导致被修改掉了。
go 不是引用传递，是指传递吗？
万事不决问google,贴一段stackoverflow的问题 are-slices-passed-by-value
package main
import "fmt"
func main() {
x := []int{1, 10, 100, 1000}
double(x)
fmt.Println(x) // ----> 3 will print [2, 20, 200, 2000] (original slice changed)
}
func double(y []int) {
fmt.Println(y) // ----> 1 will print [1, 10, 100, 1000]
for i := 0; i < len(y); i++ {
y[i] *= 2
}
fmt.Println(y) // ----> 2 will print [2, 20, 200, 2000] (copy slice + under array changed)
}
type SliceHeader struct {
Data uintptr
Len int
Cap int
}
按理来讲，main 函数里面的x 应该还是原样呀，对吧，为啥double了？贴一段最高票的答案
Everything in Go is passed by value, slices too. But a slice value is a header, describing a contiguous section of a backing array, and a slice value only contains a pointer to the array where the elements are actually stored. The slice value does not include its elements (unlike arrays).
So when you pass a slice to a function, a copy will be made from this header, including the pointer, which will point to the same backing array. Modifying the elements of the slice implies modifying the elements of the backing array, and so all slices which share the same backing array will “observe” the change.
翻译过来就是go 是值传递，没有问题的，slice也是值传递，不过因为slice是一个header，所以传递的是一个header，而不是一个slice，所以修改slice的值，会修改数组的值，所以所有共享同一个数组的slice都会观察到这个修改。
回过来我们的问题
可以发现右侧的5-8-4-5 是一个符合答案的结果，但当遍历右侧子树的时候，5-8-4-1 的时候，5-8-4-1 与5-8-4-5 共享了一个5-8-4 的parents nodes，当把1 添加到5-8-4 的nodes的时候，5-8-4-5 的序列被改成了5-8-4-1。
怎么解决？
当前节点的序列应该都创建一个新的slice，然后把当前节点添加到这个新的slice里面，然后把这个新的slice添加到结果集里面。
var result [][]int
var ch = make(chan *TreeNode, 100)
var sumChan = make(chan int, 100)
var nodes = make(chan []int, 100)
for len(ch) > 0 {
for i := 0; i < len(ch); i++ {
//获取当前节点
cur := <-ch
//获取父节点的总和
parentSum := <-sumChan
//获取父节点的所有路径节点序列
parents := <-nodes
//当前节点的总和
curSum := parentSum + cur.Val
//当前节点的序列
curNodes := append(parents, cur.Val)
//新增一个nodes slice，复制之前的序列，并且更改传递
resNodes := make([]int, len(curNodes))
copy(resNodes, curNodes)
if cur.Left == nil && cur.Right == nil {
if curSum == targetSum {
// 添加当前节点序列到结果集
result = append(result, resNodes)
}
} else {
if cur.Left != nil {
ch <- cur.Left
sumChan <- cur.Val + parentSum
nodes <- resNodes
}
if cur.Right != nil {
ch <- cur.Right
sumChan <- cur.Val + parentSum
nodes <- resNodes
}
}
}
}
结语
每一门语言都不是完美的，最好的语言，应该尽量简化理解成本，而不是让用户自己去理解。每个语言的设计也都是有tradeoffs的，有些语言的设计是为了提高性能，有些语言的设计是为了提高可读性。
高级语言是在人类和汇编语言之间的桥梁，汇编语言是高级语言和计算机之前的桥梁。
自然语言是人类的语言，会有新的AI将人类的语言变成计算机的语言吗？这些中间层，可能效率低一些，但他是增加了人类的参与度的，普适度的。