Go切片踩坑记录

今日刷力扣，写一个二叉树的前序遍历代码如下：

package BiTree

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

func preorderTraversal(root *TreeNode) []int {
    var result []int
    traversal(root, result)
    return result
}

func traversal(node *TreeNode, result []int) {
    if node == nil {
        return
    }
    result = append(result, node.Val)
    traversal(node.Left, result)
    traversal(node.Right, result)
}

go的传递方式只有值传递一种，但切片是引用类型，在调用函数时将实际参数的地址传递到函数中，那么在函数中对参数所进行的修改，将影响到实际参数。

但是本题力扣上运行时输出结果却为[]（正确输出：1 2 3），便引起了笔者的思考

首先打印result前后的地址

func preorderTraversal(root *TreeNode) []int {
    var result []int
    fmt.Printf("初始地址：%p\n", result)
    traversal(root, result)
    fmt.Printf("返回的地址：%p\n", result)
    return result
}

func traversal(node *TreeNode, result []int) {
    fmt.Printf("传入函数的地址为：%p\n", result)
    if node == nil {
        return
    }
    result = append(result, node.Val)
    fmt.Println(result)
    fmt.Printf("append后的地址为：%p\n", result)
    traversal(node.Left, result)
    traversal(node.Right, result)
}

初始地址：0x0
传入函数的地址为：0x0
[1]
append后的地址为：0xc0000140a0
传入函数的地址为：0xc0000140a0
传入函数的地址为：0xc0000140a0
[1 2]
append后的地址为：0xc0000140b0
传入函数的地址为：0xc0000140b0
[1 2 3]
append后的地址为：0xc000074020
传入函数的地址为：0xc000074020
传入函数的地址为：0xc000074020
传入函数的地址为：0xc0000140b0
返回的地址：0x0

从第二行可以看出传递的确实是指针，在递归的时候result的值确实再改变，而值得我们注意的是append前后地址的变化。

当切片需要扩容时会创建新的数组，这会导致和原有切片的分离，也就是说现在改变的切片已经不再是原来的地址了，但是append时我们将它重新赋给了result，所以traversal函数内的result始终指向正确的地址，而preorderTraversal中的result仍时原来的地址，所以最终的结果为[]，关于切片的底层实现详见链接。

解决方法：

第一种是traversal中返回result

func preorderTraversal(root *TreeNode) []int {
    var result []int
    result = traversal(root, result)
    return result
}

func traversal(node *TreeNode,result []int) []int {
    if node == nil {
        return result
    }
    result = append(result, node.Val)
    result = traversal(node.Left, result)
    result = traversal(node.Right, result)
    return result
}

第二种为力扣给出的题解

func preorderTraversal(root *TreeNode) (vals []int) {
    var preorder func(*TreeNode)
    preorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        vals = append(vals, node.Val)
        preorder(node.Left)
        preorder(node.Right)
    }
    preorder(root)
    return
}