//多种递归融合的方法，考察递归的认识，尤其递归的参数

public class Solution {
    
    
    public int ret =0;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */
    public int FindPath (TreeNode root, int sum) {
        // write code here

        //多层递归，这里容易出错！！
        if(root == null){
            return ret;
        }
        //any start ,any end;
        deepSearch(root,sum); //root start;


        //child start; this is difference ,填入的和也很讲究！！
        //非常容易出错
                //非常容易出错
                        //非常容易出错
        
        FindPath(root.left , sum );
        FindPath(root.right, sum );

        //容易忘返回全局变量

        return ret;
    }

    public void deepSearch(TreeNode root, int sum){
        if(root == null)
            return ;
        
        //not consider the leaf
        if( sum == root.val){
            ret++;
        }

        //still search
        deepSearch(root.left, sum - root.val);
        deepSearch(root.right, sum - root.val);

    }
}

// 利用hashmap的java解法1
// 参考https://blog.nowcoder.net/n/9f3db96916704e1cae1b7ff4956d1bd2
import java.util.*;

//https://www.runoob.com/java/java-hashmap.html
//hashMap.get[] //这个查询就是关键哈。
//HashMap<Integer, String> Sites = new HashMap<Integer, String>(); sites.containsKey(1)
//hashMap[]++;
//hashMap[]--;
public class Solution {


    HashMap<Integer, Integer> mMap = new HashMap<Integer, Integer>();
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */
    public int FindPath (TreeNode root, int sum) {
        // write code here

        if(root == null)
        return 0;

        //mMap[0]=1;
        mMap.put(0,1);
        return deepS(root,sum,0);
    }
    public int deepS(TreeNode root, int sum , int last){
        if(root == null){
            return 0;
        }
        int lastSum = last + root.val;

        //待思考这个位置,非常难
        int res = 0;

        //注意 谁减去谁，还有map的引用
        if( mMap.containsKey(lastSum - sum) == true){
            //res+=mMap[lastSum - sum ];
            res += mMap.get(lastSum-sum);
        }
        mMap.put(lastSum, mMap.getOrDefault(lastSum,0)+1);

        //mMap[lastSum]++;

        res += deepS(root.left, sum, lastSum);
        res += deepS(root.right,sum ,lastSum);

        //mMap[lastSum]--;
        mMap.put(lastSum, mMap.getOrDefault(lastSum,0)-1);

        return res;
        

    }

}

//参考的C++ map的写法，减少递归的那种写法

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);
    }
};

//C++ 多种递归的参考，非自己实现
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;
    }
};