#class TreeNode:
#  def __init__(self, val, left=None, right=None):
#    self.val = val
#    self.left = left
#    self.right = right

class Solution:

  def __init__(self):
    # the result counter 
    self.counter = 0 
    
  '''
    node = the node to process 
    path = top to down path of the nodes in the current recursion
    target = the target sum 
    add = accumulative addition 
    start = start index 
    end = end index
  '''
  def dfs(self, node, path, target, add, start, end):
    if not node:
      return 

    # append the new node to the path and end
    path.append(node.val)
    add += node.val

    # if the node itself = target
    if node.val == target:
      self.counter += 1
    else:  
      # else find a sub-path "moving window" = target. and move the start index
      while add > target:
        add -= path[start]
        start += 1
      if add == target:
        self.counter += 1
        start = end

    # dfs to the left and cleanup node.left after the recursion
    if node.left:
      self.dfs(node.left, path, target, add, start, end + 1)
      path.pop()
    
     # dfs to the right and cleanup node.right after the recursion
    if node.right:
      self.dfs(node.right, path, target, add, start, end + 1)
      path.pop()

  def countPaths(self, root, S):
    self.dfs(root, [], S, 0, 0, 0)
    return self.counter