LC437 - 路径总和 III

package BinaryTree

func pathSum(root *TreeNode, targetSum int) int {
    hashMap := make(map[int]int)
    hashMap[0] = 1
    cnt := 0
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, sum int) {
        if node == nil {
            return
        }
        sum += node.Val
        cnt += hashMap[sum-targetSum]
        hashMap[sum]++
        dfs(node.Left, sum)
        dfs(node.Right, sum)
        hashMap[sum]--
    }
    dfs(root, 0)
    return cnt
}

根据题目对路径的定义，本题实质上是树版的LC560。

需要特别注意的是此处必须在DFS的过程中对哈希表进行回溯。