2021-12-15： 路径总和 III。给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。力扣437。
答案2021-12-15：
时间紧，具体见代码。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
root := &TreeNode{val: 1}
root.left = &TreeNode{val: 2}
root.right = &TreeNode{val: 3}
ret := pathSum(root, 3)
fmt.Println(ret)
}
type TreeNode struct {
val int
left *TreeNode
right *TreeNode
}
func pathSum(root *TreeNode, sum int) int {
preSumMap := make(map[int]int)
preSumMap[0] = 1
return process(root, sum, 0, preSumMap)
}
// 返回方法数
func process(x *TreeNode, sum int, preAll int, preSumMap map[int]int) int {
if x == nil {
return 0
}
all := preAll + x.val
ans := 0
if _, ok := preSumMap[all-sum]; ok {
ans = preSumMap[all-sum]
}
if _, ok := preSumMap[all]; !ok {
preSumMap[all] = 1
} else {
preSumMap[all] = preSumMap[all] + 1
}
ans += process(x.left, sum, all, preSumMap)
ans += process(x.right, sum, all, preSumMap)
if preSumMap[all] == 1 {
delete(preSumMap, all)
} else {
preSumMap[all] = preSumMap[all] - 1
}
return ans
}
执行结果如下：
左神java代码
