Lstmxx的空间

437. 路径总和 III

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

链接

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function pathSum(root: TreeNode | null, targetSum: number): number {
  
  const pathMap: Map<number, number> = new Map()
  pathMap.set(0, 1)
  return traverse(root, pathMap, targetSum, 0)
};

function traverse(node: TreeNode, pathMap: Map<number, number>, target: number, curr: number): number {
    if (node === null) return 0
    let res = 0
    curr += node.val
    res += pathMap.get(curr - target) || 0
    pathMap.set(curr, (pathMap.get(curr) || 0) + 1)
    res += traverse(node.left, pathMap, target, curr)
    res += traverse(node.right, pathMap, target, curr)
    pathMap.set(curr, pathMap.get(curr) - 1)
    return res
  }