https://leetcode.com/problems/path-sum-iii/

pathSumIII.go

package main

// TreeNode Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func _pathSum(root *TreeNode, remainder, target int, memo map[int]int) int {

	if root == nil {
		return 0
	}

	remainder += root.Val
	result := memo[remainder-target]

	memo[remainder]++

	result += _pathSum(root.Left, remainder, target, memo)
	result += _pathSum(root.Right, remainder, target, memo)

	memo[remainder]--
	return result
}

func pathSum(root *TreeNode, sum int) int {
	m := map[int]int{0: 1}
	return _pathSum(root, 0, sum, m)
}