1.前言
今天在力扣上写算法，遇到了一个比较"奇怪"的错误。由于自己使用了递归+切片，导致一开始没有看明白，直到在自己电脑上进行debug的时候才反应过来，原因出在了哪里？下面会先进行错误的分析和纠正，之后进行切片底层原理的探索，由于篇幅较长，为了小伙伴们的阅读体验，分为上下两篇进行。
2. 算法题目 + 错误代码
力扣题目：113. 路径总和 II
自己的题解:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pathSum(root *TreeNode, targetSum int) [][]int {
var array [][]int
if root == nil{
return array
}
var addPath func(node *TreeNode,sum int,path []int)
addPath = func(node *TreeNode,sum int,path []int){
if node.Left == nil && node.Right == nil{
sum += node.Val
if sum == targetSum{
path = append(path,node.Val)
array = append(array,path)
//打印的值,下图中的标准输出
fmt.Println(path,array)
}
return
}
sum += node.Val
path = append(path,node.Val)
if node.Left != nil{
addPath(node.Left,sum,path)
}
if node.Right != nil{
addPath(node.Right,sum,path)
}
}
addPath(root,0,[]int{})
return array
}运行错误示例和图示：
3. 错误分析
我们可以发现在代码中 node节点左右都为空的判断中打印输出的明明是[[-6,-3,-6,-6]]；但是最后输出却变成了[[-6,-3,-6,-5]]，导致输出结果不符合预期。第一次看到这样的情况，感觉很奇怪，重新梳理一遍自己代码的逻辑，没有发现错误。最后将猜测可能是切片容器的问题，于是在自己本地进行debug,发现果然如此。
这其中隐藏着切片的两个底层实现：
- 切片是引用类型，会进行引用传递；
- 切片会随着元素数量的增加，进行扩容，改变其的底层数组的指向；
在我的算法实现中最终的返回值是一个二维切片，在二叉树遍历的过程中不断将路径上的节点加入
到一维切片path中。如果最后遍历的是叶子节点并且路径上的所有值的总和等于要求的值，就将一维切片path直接加入到二维切片中。而问题就出现在这里，我是直接将一维切片加入到二维切片中的，而切片是引用类型，后续对path切片的修改会影响到已加入二维切片中的切片（注意：这里的影响不是一定的，需要加一个条件，和加入二维切片中的path指向的是同一个底层数组的切片才会进行影响），这也是为什么我之前110个测试能够通过，而这一个无法通过的原因，是有一定的概率的。
因为切片是引用类型的，所以导致了已经加入二维切片中的一维切片被修改了，那么，为什么修改后的结果是[[-6,-3,-6,-5]]而不是[[-6,-3,-6,-5,1]]等具有其他的切片呢？
这是因为切片的扩容机制，导致了指向的底层数组发生了变更，具体如下图：
4.总结：
导致我们最后输出答案是[[-6,-3,-6,-5]]的原因如下：
- 切片是引用类型，会进行引用传递；
- 切片会随着元素数量的增加，进行扩容，改变其的底层数组的指向；
现在再看这两句话，是不是清晰明确了很多。
下一篇文章将介绍关于切片的底层扩容机制
5.正确代码：
我们不要将符合条件的path切片直接加入到二维切片中，而是要进行copy复制，防止发生引用传递；
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pathSum(root *TreeNode, targetSum int) [][]int {
var array [][]int
if root == nil{
return array
}
var addPath func(node *TreeNode,sum int,path []int)
addPath = func(node *TreeNode,sum int,path []int){
if node.Left == nil && node.Right == nil{
sum += node.Val
if sum == targetSum{
path = append(path, node.Val)
//这里对path的值进行复制
copyPath := make([]int, len(path))
copy(copyPath, path)
array = append(array, copyPath)
}
return
}
sum += node.Val
path = append(path,node.Val)
if node.Left != nil{
addPath(node.Left,sum,path)
}
if node.Right != nil{
addPath(node.Right,sum,path)
}
}
addPath(root,0,[]int{})
return array
}通过通过
6.本地测试代码：
本地测试代码的示例做了一些变更，大家可以自行测试：
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func Constructor(value int, leftNode *TreeNode, rightNode *TreeNode) *TreeNode {
return &TreeNode{
Val: value,
Left: leftNode,
Right: rightNode,
}
}
func main() {
node_61 := Constructor(-6, nil, nil)
node1 := Constructor(1, nil, nil)
node7 := Constructor(7, nil, nil)
node_5 := Constructor(-5, node1, node7)
node_62 := Constructor(-6, node_61, node_5)
node11 := Constructor(11, node_61, node_5)
node4 := Constructor(-6, nil, nil)
node0 := Constructor(-6, node4, node11)
node_3 := Constructor(-3, node_62, node0)
node_63 := Constructor(-6, nil, node_3)
fmt.Println("result", pathSum(node_63, -21))
}
func pathSum(root *TreeNode, targetSum int) [][]int {
var array [][]int
if root == nil {
return array
}
var addPath func(node *TreeNode, sum int, path []int)
addPath = func(node *TreeNode, sum int, path []int) {
if node.Left == nil && node.Right == nil {
sum += node.Val
if sum == targetSum {
//未修改哈!
path = append(path, node.Val)
array = append(array, path)
fmt.Println(path, array)
}
return
}
sum += node.Val
path = append(path, node.Val)
if node.Left != nil {
addPath(node.Left, sum, path)
}
if node.Right != nil {
addPath(node.Right, sum, path)
}
}
addPath(root, 0, []int{})
return array
}
