路径总和Ⅱ

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

典型的找出所有路径的题目。(把已有路径放在递归的参数里面)

最开始写的代码死活不对，这是因为res = append(res, append(localPath, node.Val))这里，不应该直接append这个值，而是应该append它的一个copy。

浅拷贝 深拷贝问题，可以用这个库barkimedes/go-deepcopy: A Golang package for doing a deep copy for (just about) anything (github.com)

// 出问题的代码
func sum(array []int) int {
    result := 0
    for _, v := range array {
        result += v
    }
    return result
}

func pathSum(root *TreeNode, targetSum int) [][]int {
    res := [][]int{}
    var help func(node *TreeNode, localPath []int)
    help = func(node *TreeNode, localPath []int) {
        if node == nil {
            return
        }
        localSum := sum(localPath)
        if localSum+node.Val == targetSum && node.Left == nil && node.Right == nil {
            res = append(res, append(localPath, node.Val))
            return
        }
        localPath = append(localPath, node.Val)
        help(node.Left, localPath)
        help(node.Right, localPath)
    }
    help(root, []int{})
    return res
}

// 修改了深拷贝
func sum(array []int) int {
    result := 0
    for _, v := range array {
        result += v
    }
    return result
}

func copySlice(slice []int) []int {
    sliceCopy := make([]int, len(slice))
    copy(sliceCopy, slice)
    return sliceCopy
}

func pathSum(root *TreeNode, targetSum int) [][]int {
    res := [][]int{}
    var help func(node *TreeNode, localPath []int)
    help = func(node *TreeNode, localPath []int) {
        if node == nil {
            return
        }
        localSum := sum(localPath)
        if localSum+node.Val == targetSum && node.Left == nil && node.Right == nil {
            res = append(res, copySlice(append(localPath, node.Val)))
            return
        }
        localPath = append(localPath, node.Val)
        help(node.Left, localPath)
        help(node.Right, localPath)
    }
    help(root, []int{})
    return res
}