嵌套递归法

• 双层递归：check递归函数检测从root点出发是否存在符合的路径
• FindPath递归，遍历树的节点作为起点
• 注意check函数结束递归的条件是空节点，不是sum==0,如果下一个节点值为0，那么可以存在两条路径，而函数提前结束。
• 会存在重复计算

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */
    int a=0;
    void check(TreeNode* root,int sum)
    {
        
        if(!root)
        {
            return;
        }   
        if(sum-root->val==0)
        {
            a+=1;
        }
        check(root->left,sum-root->val);
        check(root->right,sum-root->val);
    }
    int FindPath(TreeNode* root, int sum) {
        // write code here
        if(!root)
        {
            return 0;//no path
        }
        check(root,sum);
        FindPath(root->left,sum);
        FindPath(root->right,sum);
        return a;
    }
};

哈希+一次递归 --没懂

• 没懂

class Solution {
public:
    //记录路径和及条数
    unordered_map<int, int> mp; 
    //last为到上一层为止的累加和
    int dfs(TreeNode* root, int sum, int last){ 
        //空结点直接返回
        if(root == NULL) 
            return 0;
        int res = 0;
        //到目前结点为止的累加和
        int temp = root->val + last; 
        //如果该累加和减去sum在哈希表中出现过，相当于减去前面的分支
        if(mp.find(temp - sum) != mp.end())  
            //加上有的路径数
            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) { 
        //路径和为0的有1条
        mp[0] = 1; 
        return dfs(root, sum, 0);
    }
};