437. Path Sum III

Leetcode link

题目简介

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */

题目给我们一个二叉树的根节点 root 以及一个数字 targetSum

题目要求我们找到路径中节点之和为 targetSum 的路径个数

合法路径定义：必须从根节点到叶子节点，且不必包含根节点或叶子节点

解题思路

这题的暴力解法思路是：通过 dfs 遍历出每一条从根到叶子的路径，然后对这些路径用滑动窗口找到窗口内节点之和为 targetSum 的窗口数量

在暴力的基础上，我们可以使用前缀和的方法来减少复杂度

步骤：

1. 使用 dfs 遍历路径，并且在遍历每个节点的时候记录前缀和 prefixSum，并且用一个 prefixSumMap 记录该前缀和出现的次数
2. 在 prefixSumMap 中查找 prefixSum - targetSum 出现的次数，这个次数代表了当前路径下节点之和为 targetSum 的子路径个数
3. 依次遍历左右子树
4. 左右子树回溯的时候记得要从 prefixSumMap 把当前前缀和的个数 - 1

prefixSumMap 的初始状态是 {0: 1} 代表当 prefixSum === targetSum 的时候出现了 1 个路径

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */
var pathSum = function(root, targetSum) {
    // {prefixSum: count}
    const prefixSumMap = new Map()
    // if prefixSum === targetSum, then we get 1 path
    prefixSumMap.set(0, 1)

    const dfs = (node, sum) => {
        if(!node) {
            return 0
        }

        sum += node.val
        let count = prefixSumMap.get(sum - targetSum) || 0

        prefixSumMap.set(sum, (prefixSumMap.get(sum) || 0) + 1)
        count += dfs(node.left, sum)
        count += dfs(node.right, sum)
        prefixSumMap.set(sum, prefixSumMap.get(sum) - 1)

        return count
    }

    return dfs(root, 0)
};