leetcode：437. 路径总和 III

题目

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

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

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

解答 & 代码

遇到“区间和”的问题就可以用到“前缀和”来解题。
思路同：
[中等] 560. 和为 K 的子数组
注意：记得哈希表初始化存入 (0, 0)，代表有一条空路径，路径和为 0

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int pathCnt = 0;        // 二叉树中和为 targetSum 的路径数目（起点不限于根节点）
    int prePathSum = 0;        // 从根节点到当前节点的路径和（即前缀和）
    // 哈希表，key = 前缀和，val = 对应的路径数目。前缀和指的是从根节点到某个节点的路径和
    unordered_map<int, int> preSumCntMap;
    // 深度优先遍历
    void dfs(TreeNode* root, int targetSum)
    {
        if(root == nullptr)
            return;
        // 前序位置：
        prePathSum += root->val;    // 更新根节点到当前节点的路径和
        // 在哈希表中查找，从根节点开始路径和/前缀和为 prePathSum - targetSum 的路径数目
        // 就是路径和为 targetSum 的路径条数（起点不限于根节点），更新 pathCnt
        if(preSumCntMap.find(prePathSum - targetSum) != preSumCntMap.end())
            pathCnt += preSumCntMap[prePathSum - targetSum];
        // 在哈希表中更新 从根节点开始、路径和为 prePathSum 的路径数目
        if(preSumCntMap.find(prePathSum) == preSumCntMap.end())
            preSumCntMap[prePathSum] = 1;
        else
            preSumCntMap[prePathSum] += 1;
        // 递归处理左、右子树
        dfs(root->left, targetSum);
        dfs(root->right, targetSum);
        // 后序位置：要退出当前节点了，需撤销当前节点对 prePathSum 及 哈希表的改动
        preSumCntMap[prePathSum] -= 1;
        if(preSumCntMap[prePathSum] == 0)
            preSumCntMap.erase(prePathSum);
        prePathSum -= root->val;
    }
public:
    int pathSum(TreeNode* root, int targetSum) {
        // 初始时在哈希表中存入 <0, 1>，代表空路径，不含节点（从根节点开始、路径和为 0）
        preSumCntMap[0] = 1;
        dfs(root, targetSum);
        return pathCnt;
    }
};

复杂度分析：设二叉树节点数 N

• 时间复杂度 O(N)
• 空间复杂度 O(log N)：栈空间取决于递归深度，即二叉树的高度

执行结果：

执行结果：通过
执行用时：16 ms, 在所有 C++ 提交中击败了 76.32% 的用户
内存消耗：19.1 MB, 在所有 C++ 提交中击败了17.60% 的用户

更新：leetcode 增加了测试用例，路径和可能超过 int 范围，因此需要修改为 long 类型
另：unordered_map 对于不存在的 key，查找并使用时会自动赋值 value 为 0，因此上述代码其实可以简化

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int result;
    unordered_map<long, int> preSumCntMap;
    void backTrace(TreeNode* root, long pathSum, int targetSum)
    {
        if(root == nullptr)
            return;
        // 选择
        pathSum += root->val;
        result += preSumCntMap[pathSum - targetSum];
        ++preSumCntMap[pathSum];
        // 递归回溯
        backTrace(root->left, pathSum, targetSum);
        backTrace(root->right, pathSum, targetSum);
        // 撤销选择
        --preSumCntMap[pathSum];
        pathSum -= root->val;
    }
public:
    int pathSum(TreeNode* root, int targetSum) {
        result = 0;
        preSumCntMap[0] = 1;    // 注意初始存入空路径！即存在一条路径和为 0 
        backTrace(root, 0, targetSum);
        return result;
    }
};