描述

题目描述

首先是给定了我们的一颗树, 我们要判断有多少条的路径可以满足我们路径的总和的值等于我们的$sumsum$, 然后我们根节点可以是任意的, 然后我们必须是从父亲节点到孩子节点

题解

解法一: 每一次都作为根节点

实现思路

我们穷举的所有的节点, 然后以每一个节点检测向下延申的路径有多少种, 我们遍历每一个节点的值, 然后向上传, 这样我们把答案汇总了就是我们最后的结果

然后我们定义我们的$dfsdfs$就是我们的表示的是从我们当前的节点为起点向下且满足路径总和为$valval$的路径的数目, 我们求总和即可

然后我们对于某一个节点向下的所有路径的总和就是等于我们当前的这个节点的左右孩子的路径之和, 那么我们就可以写出以下的代码

代码实现

class Solution {
   public:
    int dfs(TreeNode *root, int sum) {
        if (root == nullptr) return 0;
        int res = 0;
        if (root->val == sum) res += 1;
        // 如果我们当前的这个位置正好满足, 我们让我们的答案加一
        res += dfs(root->left, sum - root->val);
        res += dfs(root->right, sum - root->val);
        // 这个分别递归判断左右孩子
        return res;
    }
    // 这个就是判断我们一个节点有多少满足的
    int FindPath(TreeNode *root, int sum) {
        if (root == nullptr) return 0;
        int res = dfs(root, sum);
        // 当前这个位置的值
        res += FindPath(root->left, sum);
        res += FindPath(root->right, sum);
        // 寻找左右孩子
        return res;
    }
};

时空复杂度分析

时间复杂度: $O(n^2)O(n\; ^\; 2)$

理由如下: 我们对于每一个节点, 求该节点为起点的路径数的时候, 我们都需要遍历以该起点为根节点的子树上的所有的节点, 所以我们求该路径的花费的最大时间是$O(n)O(n)$的, 然后我们对每一个节点都求一次该节点为起点的路径数目, 所以我们的时间复杂度是$O(n^2)O(n\; ^\; 2)$

空间复杂度: $O(n)O(n)$

理由如下: 我们系统的递归栈的深度最坏为$nn$

解法二: 前缀和

实现思路

首先明确我们的这个前缀和的概念: 一个节点的前缀和就是该节点到根之间的路径和

前缀和的意义: 对于同一个路径的两个节点, 前缀和之差其实就是两个节点之间的路径和

我们如何存储这些, 我们需要用到哈希表的这个结构, 然后因为我们只有同一条路径上的节点间的前缀和做差才有意义, 所以当前的节点搞定之后要移除这个前缀和再进入下一个分支路径

图解代码

前缀和的意义:

对于本题的作用:

代码实现

class Solution {
    unordered_map<int, int> mp;
    int res = 0;

   public:
    void dfs(TreeNode *root, int sum, int tmp) {
        if (root == nullptr) return;
        tmp += root->val;
        // 更新前缀和
        if (mp[tmp - sum]) res += mp[tmp - sum];
        // 当前路径存在以当前节点为终点的和为sum的子路径
        mp[tmp] += 1;
        dfs(root->left, sum, tmp);
        dfs(root->right, sum, tmp);
        // 递归的寻找我们的左右孩子
        mp[tmp] -= 1;
        // 回溯
    }
    int FindPath(TreeNode *root, int sum) {
        mp[0] = 1;
        // 前缀和为0的路只有一条, 啥也不选
        dfs(root, sum, 0);
        return res;
    }
};

时空复杂度分析

时间复杂度: $O(n)O(n)$

理由如下: 事实上我们这里只是需要简单的遍历一次我们的二叉树即可满足我们条件, 比方法一减少了很多无用的重复计算

空间复杂度: $O(n)O(n)$

理由如下: 树形结构最坏情况下会退化成为一条链, 所以我们系统递归栈的深度可能会是$nn$, 另一方面我们还开了一个哈希表用于存储和记录前缀和