给定一个二叉树的根节点
root，和一个整数targetSum，求该二叉树里节点值之和等于targetSum的 路径 的数目。路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
编辑
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
提示:
- 二叉树的节点个数的范围是
[0,1000]-109 <= Node.val <= 109-1000 <= targetSum <= 1000
思路：
dfs递归，将每个节点都当做起始的根节点对待
- 该题可以通过在子函数中增加额外入参 【
sum累加和】来做加法，通过比较【当前累加和】是否和【目标和】相等：if sum + node.Val == targetSum - 也可以通过对已有入参
targetSum做减法，来比较【当前节点值】是否和【不断消减的目标和】相等：if node.Val == target
注意：处理中间层逻辑时，即使找到了一条目标路径，也不立即 return，继续找。因为 Node.val 有可能为负数，后续有可能再减为目标和 targetSum。
时间复杂度：
O(N^2)，其中 N 为该二叉树节点的个数。对于每一个节点，求以该节点为起点的路径数目时，则需要遍历以该节点为根节点的子树的所有节点，因此求该路径所花费的最大时间为 O(N)，我们会对每个节点都求一次以该节点为起点的路径数目，因此时间复杂度为 O(N^2)
空间复杂度：
O(N)，考虑到递归需要在栈上开辟空间。
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/// 参考：https://leetcode.cn/problems/path-sum-iii/solutions/109711/custerxue-xi-bi-ji-er-cha-shu-de-di-gui-he-dfs-by-/?languageTags=golang/***************************** 方法1 通过sum额外入参做加法 *****************************/// 写法1：因为后续的测试用例会覆盖之前的结果，所以这里的res不能在_pathSum初始化，需要在pathSum中初始化varresintfuncpathSum(root*TreeNode, targetSumint) int { res=0// 多个测试用例下，避免结果被后续测试用例的结果覆盖_pathSum(root, targetSum, 0) returnres} func_pathSum(root*TreeNode, targetSum, sumint) { ifroot==nil { return } dfs(root, targetSum, sum) _pathSum(root.Left, targetSum, sum) _pathSum(root.Right, targetSum, sum) } funcdfs(node*TreeNode, targetSum, sumint) { ifnode==nil { return } sum+=node.Valifsum==targetSum { res++ } dfs(node.Left, targetSum, sum) dfs(node.Right, targetSum, sum) } // 写法2：不另外添加_pathSum方法调用，但是dfs中就需要将cnt结果返回才行varresintfuncpathSum(root*TreeNode, targetSumint) int { res=0// 多个测试用例下，避免结果被后续测试用例的结果覆盖ifroot==nil { return0 } returndfs(root, targetSum, 0) +pathSum(root.Left, targetSum) +pathSum(root.Right, targetSum) } funcdfs(node*TreeNode, targetSum, sumint) int { ifnode==nil { return0 } sum+=node.Valifsum==targetSum { res++ } dfs(node.Left, targetSum, sum) dfs(node.Right, targetSum, sum) returnres} /***************************** 方法2 通过targetSum入参做减法 *****************************/// 写法3：因为后续的测试用例会覆盖之前的结果，所以这里的res不能在_pathSum初始化，需要在pathSum中初始化varresintfuncpathSum(root*TreeNode, targetSumint) int { res=0_pathSum(root, targetSum) returnres} func_pathSum(root*TreeNode, targetSumint) int { // res = 0ifroot==nil { return0 } dfs(root, targetSum) _pathSum(root.Left, targetSum) // 分别以root的左右孩子节点为根节点，并不断的继续下探_pathSum(root.Right, targetSum) returnres} funcdfs(node*TreeNode, targetint) { ifnode==nil { return } // 这里因为不限定从根节点到叶节点，所以不需要该条件：if node.Left == nil && node.Right == nilifnode.Val==target { res++ } dfs(node.Left, target-node.Val) dfs(node.Right, target-node.Val) } // 写法4：不另外添加_pathSum方法调用，但是dfs中就需要将cnt结果返回才行funcpathSum(root*TreeNode, targetSumint) int { ifroot==nil { return0 } returndfs(root, targetSum) +pathSum(root.Left, targetSum) +pathSum(root.Right, targetSum) } funcdfs(node*TreeNode, sumint) int { ifnode==nil { return0 } res :=0ifnode.Val==sum { res++ } res+=dfs(node.Left, sum-node.Val) res+=dfs(node.Right, sum-node.Val) returnres}
