educative.io

O(N) solution, just one top down recursive call and O(N*log(N)) space

Courses
,
#1

class CountAllPathSum {
static int count;
public static int countPaths(TreeNode root, int S) {
count =0;
getSums(root, S, pathSums);
return count;
}

private static List getSums(TreeNode cur, int S, Map<Integer, Integer> map){
List curSums = new ArrayList();
if(cur==null) return curSums;

if(cur.left == null && cur.right == null){
  if(cur.val==S)count++;
  curSums.add(cur.val);
  return curSums;
}

List<Integer> leftSum = getSums(cur.left, S, map);
List<Integer> rightSum = getSums(cur.right, S, map);

for(int n: leftSum){
  int sum = n+cur.val;
  if(sum == S) count++;
  curSums.add(sum);
}
for(int n: rightSum){
  int sum = n+cur.val;
  if(sum == S) count++;
  curSums.add(sum);
}
return curSums;

}