路径总和Ⅲ

描述

给定一个二叉树的根节点 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

提示:

二叉树的节点个数的范围是 [0,1000]
-109 <= Node.val <= 109
-1000 <= targetSum <= 1000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/path-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这道题目要求我们找到二叉树中路径和为给定值的路径数量。我们可以使用深度优先搜索（DFS）来解决这个问题。具体来说，我们可以先遍历二叉树，对于每个节点，计算以该节点为起点的路径数量，然后将所有路径数量相加即可得到答案。

在DFS的过程中，对于每个节点，我们需要判断它是否为空。如果为空，直接返回0。否则，我们需要计算以该节点为起点的路径数量。具体来说，我们可以将当前节点的值从sum中减去，然后递归遍历左右子树，将左右子树的路径数量相加，最后返回以当前节点为起点的路径数量。如果当前节点的值等于sum，那么路径数量加1。

最后，我们可以将以当前节点为起点的路径数量 + 左子树的路径数量 + 右子树的路径数量相加，就可以得到最终的答案。

C++代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if (!root) return 0; // 如果节点为空，返回0
        return dfs(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
        // 返回以当前节点为起点的路径数 + 左子树的路径数 + 右子树的路径数
    }
    
    int dfs(TreeNode* node, int sum) {
        if (!node) return 0; // 如果节点为空，返回0
        int res = 0;
        if (node->val == sum) res++; // 如果当前节点的值等于sum，路径数+1
        res += dfs(node->left, sum - node->val); // 递归遍历左子树
        res += dfs(node->right, sum - node->val); // 递归遍历右子树
        return res; // 返回以当前节点为起点的路径数
    }
};

但是提交以上代码后，提示超时了——runtime error！可能是因为在计算路径数量时，重复遍历了一些节点，导致时间复杂度增加。为了避免这种情况，我们可以使用前缀和（prefix sum）来优化算法。

具体来说，我们可以使用一个哈希表来存储前缀和出现的次数。在遍历二叉树的过程中，对于每个节点，我们可以计算从根节点到该节点的路径和，然后在哈希表中查找是否存在一个前缀和，使得当前路径和减去该前缀和等于给定的目标值。如果存在这样的前缀和，那么说明存在一条从根节点到当前节点的路径，使得路径和等于给定的目标值。

下面是使用前缀和优化的代码：

class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        unordered_map<int, int> prefixSum; // 哈希表存储前缀和出现的次数
        prefixSum[0] = 1; // 初始情况下，前缀和为0出现了1次
        return dfs(root, sum, prefixSum, 0); // 从根节点开始遍历
    }
    
    int dfs(TreeNode* node, int sum, unordered_map<int, int>& prefixSum, int curSum) {
        if (!node) return 0; // 如果节点为空，返回0
        curSum += node->val; // 计算从根节点到当前节点的路径和
        int res = 0;
        if (prefixSum.count(curSum - sum)) 
            res += prefixSum[curSum - sum]; // 如果存在一个前缀和，使得当前路径和减去该前缀和等于给定的目标值，那么说明存在一条从根节点到当前节点的路径，使得路径和等于给定的目标值
        prefixSum[curSum]++; // 将当前节点的前缀和出现次数+1
        res += dfs(node->left, sum, prefixSum, curSum); // 递归遍历左子树
        res += dfs(node->right, sum, prefixSum, curSum); // 递归遍历右子树
        prefixSum[curSum]--; // 回溯，将当前节点的前缀和出现次数-1
        return res; // 返回从根节点到当前节点的路径数量
    }
};

还是报错超时了，可能是因为在计算前缀和时，使用了递归，导致时间复杂度增加。为了避免这种情况，我们可以使用迭代来计算前缀和。

具体来说，我们可以使用一个栈来存储节点和它们的前缀和。在遍历二叉树的过程中，对于每个节点，我们可以计算从根节点到该节点的路径和，然后在栈中查找是否存在一个前缀和，使得当前路径和减去该前缀和等于给定的目标值。如果存在这样的前缀和，那么说明存在一条从根节点到当前节点的路径，使得路径和等于给定的目标值。

下面是使用迭代计算前缀和的代码：

class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        int res = 0;
        unordered_map<int, int> prefixSum; // 哈希表存储前缀和出现的次数
        prefixSum[0] = 1; // 初始情况下，前缀和为0出现了1次
        stack<pair<TreeNode*, int>> s; // 栈用于存储节点和它们的前缀和
        s.push({root, 0}); // 将根节点和前缀和0入栈
        while (!s.empty()) {
            auto [node, curSum] = s.top(); // 取出栈顶元素
            s.pop();
            if (!node) continue; // 如果节点为空，直接跳过
            curSum += node->val; // 计算从根节点到当前节点的路径和
            if (prefixSum.count(curSum - sum)) res += prefixSum[curSum - sum]; // 如果存在一个前缀和，使得当前路径和减去该前缀和等于给定的目标值，那么说明存在一条从根节点到当前节点的路径，使得路径和等于给定的目标值
            prefixSum[curSum]++; // 将当前节点的前缀和出现次数+1
            s.push({node->right, curSum}); // 将右子节点和前缀和入栈
            s.push({node->left, curSum}); // 将左子节点和前缀和入栈
            prefixSum[curSum]--; // 回溯，将当前节点的前缀和出现次数-1
        }
        return res; // 返回路径数量
    }
};

但是只通过了部分测试用例。于是，又做了修改，下面这种方法非常的简洁，用了两个递归函数，其中的一个 sumUp 递归函数是以当前结点为起点，和为 sum 的路径个数，采用了前序遍历，对于每个遍历到的节点进行处理，维护一个变量 pre 来记录之前路径之和，然后 cur 为 pre 加上当前节点值，如果 cur 等于 sum，那么返回结果时要加1，然后对当前节点的左右子节点调用递归函数求解，这是 sumUp 递归函数。而在 pathSum 函数中，我们对当前结点调用 sumUp 函数，加上对左右子结点调用 pathSum 递归函数，三者的返回值相加就是所求，参见代码如下：

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        if (!root) return 0;
        return sumUp(root, 0, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
    }
    int sumUp(TreeNode* node, long pre, int targetSum) {
        if (!node) return 0;
        long cur = pre + node->val;
        return (cur == targetSum) + sumUp(node->left, cur, targetSum) + sumUp(node->right, cur, targetSum);
    }
};