113. 路径总和 II 👌

113. 路径总和 II

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

复杂度分析

时间复杂度：O(N^2)，其中 N 是树的节点数。在最坏情况下，树的上半部分为链状，下半部分为完全二叉树，并且从根节点到每一个叶子节点的路径都符合题目要求。此时，路径的数目为 O(N)，并且每一条路径的节点个数也为 O(N)，因此要将这些路径全部添加进答案中，时间复杂度为 O(N^2)
空间复杂度：O(N)，其中 N 是树的节点数。空间复杂度主要取决于栈空间的开销，栈中的元素个数不会超过树的节点数。

//递归:通过一个 slice=tmp 记录中间路径结果
var res [][]int
func pathSum(root *TreeNode, sum int) [][]int {
    res = [][]int{}
    path := []int{}
    dfs(root, sum, path)
    return res
}
func dfs(root *TreeNode, sum int, path []int) {
    if root == nil {
        return
    }
    path = append(path, root.Val)    //全局变量
    if root.Left == nil && root.Right == nil && root.Val == sum {
        tmp := make([]int, len(path))    //不影响的临时变量,需要拷贝的条件是同一个切片用于二维数组的多个下标
        copy(tmp, path)                    //拷贝,避免后面的路径把它污染，所以先把当前结果拷贝出来
        res = append(res, tmp)
    }
    dfs(root.Left, sum - root.Val, path)
    dfs(root.Right, sum - root.Val, path)
}