题目

给定一个二叉树的根节点root ，和一个整数targetSum ，求该二叉树里节点值之和等于targetSum的 路径的数目

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）

  1. 输入：root = [10, 5, -3, 3, 2, nil, 11, 3, -2, nil, 1], targetSum = 8
  2. 输出：3

代码:

  1.  /**
  2.      * 参考力扣,牛逼的思想
  3.      * @param root
  4.      * @param sum
  5.      * @return
  6.      */
  7.     public int pathSum(TreeNode root, int sum) {
  8.         target = sum;
  9.         map.put(0, 1);
  10.         return getNodeCount(root, 0);
  11.     }
  14.     public int getNodeCount(TreeNode<Integer> root,int sum){
  15.         if(root==null){
  16.             return 0;
  17.         }
  18.         sum+=root.getData();
  19.         int count=map.getOrDefault(sum-target,0);
  20.         map.put(sum, map.getOrDefault(sum,0)+1);
  21.         int leftSum=getNodeCount(root.lTreeNode,sum);
  22.         int rightSum=getNodeCount(root.rTreeNode,sum);
  23.         count=count+leftSum+rightSum;
  24.         map.put(sum,map.getOrDefault(sum,0)-1);
  25.         return count;
  26.     }