力扣 路径总和 III

本题练习递归及其优化。
解法一：对于每个节点，递归的遍历其子节点。（可想而知这样会有大量重复遍历）
解法二：前缀和记录下根节点到正在访问的节点的前缀和，通过前缀和差值求满足条件的个数。复杂度降到O(N)。

要注意传到Java函数中的变量什么时候会改变什么时候不会改变，对于基本数据类型来说，当函数退出，其值一定跟原来是一样的不会改变。

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null) return 0; 
        int res = 0;
        res = dfs(root, targetSum, root.val, res);
        //System.out.println(res);
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);
        return res;
        
    }
    private static int dfs(TreeNode root, int targetSum, int sum, int res){
    if(root == null) return res;
    //System.out.println(root.val + " " + sum);
    if(sum == targetSum){
        res ++;
        //System.out.println( "fdsdfs " + res);
    }
    if(root.left != null){
         res = dfs(root.left, targetSum, sum + root.left.val, res);
    }
    if(root.right != null){
        res = dfs(root.right, targetSum, sum + root.right.val, res);
    }
    return res;
    }
}

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        int res = 0;
        int[] a = new int[1005];
        int tnt = 0;
        res = dfs(root, targetSum, a, tnt, res);
        return res;
    }
    private static int dfs(TreeNode root, int targetSum, int[] a, int tnt, int res){
        if(root == null) return res;
        if(tnt == 0){
           a[tnt] = root.val; 
        } else{
            a[tnt] = a[tnt - 1] + root.val;
        }
          
        for(int i = 0; i < tnt; i ++){
            if((a[tnt] - a[i]) == targetSum){
                res ++;
            }           
        }
        if(a[tnt] == targetSum){
            res ++;
        }
        tnt ++;
        res = dfs(root.left, targetSum, a, tnt, res);
        //tnt --;
        res = dfs(root.right, targetSum, a, tnt, res);
        return res;
    }
}