给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。示例：root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8      10     /  \    5   -3   / \    \  3   2   11 / \   \3  -2   1返回 3。和等于 8 的路径有:1.  5 -> 32.  5 -> 2 -> 13.  -3 -> 11

/** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } */// the number of the paths starting from selffunction helper(root, sum) {  if (root === null) return 0;  const l = helper(root.left, sum - root.val);  const r = helper(root.right, sum - root.val);  return l + r + (root.val === sum ? 1 : 0);}/** * @param {TreeNode} root * @param {number} sum * @return {number} */var pathSum = function (root, sum) {  // 空间复杂度O(n) 时间复杂度介于O(nlogn) 和 O(n^2)  // tag: dfs tree  if (root === null) return 0;  // the number of the paths starting from self  const self = helper(root, sum);  // we don't know the answer, so we just pass it down  const l = pathSum(root.left, sum);  // we don't know the answer, so we just pass it down  const r = pathSum(root.right, sum);  return self + l + r;};

/* * @lc app=leetcode id=437 lang=javascript * * [437] Path Sum III *//** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } */function helper(root, acc, target, hashmap) {  // see also : https://leetcode.com/problems/subarray-sum-equals-k/  if (root === null) return 0;  let count = 0;  acc += root.val;  if (acc === target) count++;  if (hashmap[acc - target] !== void 0) {    count += hashmap[acc - target];  }  if (hashmap[acc] === void 0) {    hashmap[acc] = 1;  } else {    hashmap[acc] += 1;  }  const res =    count +    helper(root.left, acc, target, hashmap) +    helper(root.right, acc, target, hashmap);  // 这里要注意别忘记了  hashmap[acc] = hashmap[acc] - 1;  return res;}var pathSum = function (root, sum) {  const hashmap = {};  return helper(root, 0, sum, hashmap);};

import collections'''class TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = right'''class Solution:    def helper(self,root,acc,target,hashmap):        if not root:            return 0        count=0        acc+=root.val        if acc==target:            count+=1        if acc-target in hashmap:            count+=hashmap[acc-target]        hashmap[acc]+=1        if root.left:            count+=self.helper(root.left,acc,target,hashmap)        if root.right:            count+=self.helper(root.right,acc,target,hashmap)        hashmap[acc]-=1        return count    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:        hashmap=collections.defaultdict(lambda:0)        return self.helper(root,0,targetSum,hashmap)