题目的主要信息：

• 给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum
• 路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点，如下图所示：

方法一：两次dfs

具体做法：

可以使用两次dfs解决，第一次dfs遍历二叉树每个结点，每个结点都作为一次根结点，第二次dfs遍历以每个结点为根的子树，查找该子树是否有路径和等于目标值的。

class Solution {
public:
    int res = 0;
    void dfs(TreeNode* root, int sum){ //dfs查询以某结点为根的路径数
        if(root == NULL)
            return;
        if(sum == root->val) //符合目标值
            res++;
        dfs(root->left, sum - root->val); //进入子节点继续找
        dfs(root->right, sum - root->val);
    }
    int FindPath(TreeNode* root, int sum) { //dfs 以每个结点作为根查询路径
        if(root == NULL) //为空则返回
            return res;
        dfs(root, sum); //查询以某结点为根的路径数
        FindPath(root->left, sum); //以其子结点为新根
        FindPath(root->right, sum);
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，其中$nn$为二叉树的结点数，两层dfs嵌套递归
• 空间复杂度：$O(n)O(n)$，每层dfs最深递归栈都只有$nn$

方法二：一次dfs+哈希表

具体做法：

两次dfs有些浪费，可以一次dfs解决。在进入以某个结点为根的子树中，向其中添加到该节点为止的路径和进入哈希表中，相当于每次分枝下都有前面各种路径和，相当于我只要查找哈希表就可以找到从中间截断的路径，而遍历完这个分枝后依次删除这个分枝在哈希表中记录的路径和，避免影响别的分枝，只有公共分枝的路径和才会一直记录在哈希表中。

class Solution {
public:
    unordered_map<int, int> mp; //记录路径和及条数
    int dfs(TreeNode* root, int sum, int last){ //last为到上一层为止的累加和
        if(root == NULL) //空结点直接返回
            return 0;
        int res = 0;
        int temp = root->val + last; //到目前结点为止的累加和
        if(mp.find(temp - sum) != mp.end())  //如果该累加和减去sum在哈希表中出现过，相当于减去前面的分支
            res += mp[temp - sum]; //加上有的路径数
        mp[temp]++; //增加该次路径和
        res += dfs(root->left, sum, temp); //进入子结点
        res += dfs(root->right, sum, temp); 
        mp[temp]--; //回退该路径和，因为别的树枝不需要这边存的路径和
        return res;
    }
    int FindPath(TreeNode* root, int sum) { 
        mp[0] = 1; //路径和为0的有1条
        return dfs(root, sum, 0);
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为二叉树的结点数，一次dfs
• 空间复杂度：$O(n)O(n)$，哈希表大小及递归栈最大为$nn$