【LeetCode热题100】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

提示:
二叉树的节点个数的范围是 [0,1000]
$-10^9<=Node.val<=10^9$
$-1000<=targetSum<=1000$

四.解题思路

解法1：推了一节课迭代发现不行，还是只能递归，依赖这个公式
每个结点新增路径值 = 左子树所有路径 + 该结点值 + 右子树所有路径 + 该结点值 + 该结点本身的值
解法2：前缀和
GPT的解释

五.代码实现

解1

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        mySun(root, targetSum);
        return num;
    }

    vector<long> mySun(TreeNode* root,int targetSum)
    {
        if(root == nullptr) return {};
        vector<long> leftRoad = mySun(root->left, targetSum);
        vector<long> rightRoad = mySun(root->right, targetSum);
        int val = root->val;
        vector<long> result;
        for(auto v : leftRoad) 
            result.push_back(v + val);
        for(auto v : rightRoad) 
            result.push_back(v + val);
        result.push_back(val);
        for(auto v : result) if(v == targetSum) num++;
        return result;       
    }
private:
    int num = 0;
};

GPT解2：

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long, int> prefixSumCount;
        prefixSumCount[0] = 1; // 初始条件：和为0的路径有1条（不选择任何节点）
        return dfs(root, 0, targetSum, prefixSumCount);
    }

private:
    int dfs(TreeNode* node, long currentSum, int targetSum, unordered_map<long, int>& prefixSumCount) {
        if (!node) return 0;

        currentSum += node->val; // 更新当前路径和
        int numPathsToCurr = prefixSumCount[currentSum - targetSum]; // 找到以当前节点结束，和为targetSum的路径数量
        prefixSumCount[currentSum]++; // 更新路径和出现的次数

        // 递归遍历左右子树
        int totalPaths = numPathsToCurr 
                        + dfs(node->left, currentSum, targetSum, prefixSumCount) 
                        + dfs(node->right, currentSum, targetSum, prefixSumCount);

        prefixSumCount[currentSum]--; // 回溯：恢复当前路径和出现的次数，为其他路径的遍历保持正确的计数

        return totalPaths;
    }
};

六.题目总结

适当用回溯+前缀和解决重复计算