13.路径总和3️⃣

• 2.12
  • long，target-node.val

class Solution {
    int sum=0;
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null) return 0;
        sum = Sum(root,targetSum);
        sum+=pathSum(root.left,targetSum);
        sum+=pathSum(root.right,targetSum);
        return sum;
    }
    public int Sum(TreeNode root,long targetSum){
        if(root==null) return 0;
        int temp=0;
        if(root.val==targetSum) temp++;
        temp += Sum(root.left,targetSum-root.val);
        temp += Sum(root.right,targetSum-root.val);
        return temp;
    }
}

• 1.30

  • 想起来两层递归，但是不用声明全局 sum，每次在小递归中初始化 count=0，记得加上递归返回的结果

• 1.18

  • 有点难度，依旧没做出来，但是想到了小递归那个

• 11.12

  • 两层递归,确实没想出来
    • 先从root开始大的,root中递归target-val
    • 再在大的上递归root.left和root.right
    • 答案有点舒适
    • 第二个递归target必须为long,可能会溢出!(比如-10000-10000)

 
 */
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null) return 0;
        int res = countForm(root,targetSum);
        res+=pathSum(root.left,targetSum);
        res+=pathSum(root.right,targetSum);
        return res;
    }
    public int countForm(TreeNode node,long target){
        if(node==null) return 0;
        int count=0;
        if(node.val ==target) count++;
        count+=countForm(node.left,target-node.val);
        count+=countForm(node.right,target-node.val);
        return count;
    }
}

• 暴力递归,先递归root,在递归子节点,当成root
• 前缀和+回溯法我不看