/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     public int val;

 *     public TreeNode left;

 *     public TreeNode right;

 *     public TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public int PathSum(TreeNode root, int sum)

        {

            if (root == null)

            {

                return ;

            }

            return PathSumFrom(root, sum) + PathSum(root.left, sum) + PathSum(root.right, sum);

        }

        private int PathSumFrom(TreeNode node, int sum)

        {

            if (node == null)

            {

                return ;

            }

            return (node.val == sum ?  : )

                + PathSumFrom(node.left, sum - node.val) + PathSumFrom(node.right, sum - node.val);

        }

}

 class Solution:

     def pathSum(self, root: 'TreeNode', sum: 'int') -> 'int':

         if root == None:

             return

         return self.pathSumWithRoot(root,sum) + self.pathSum(root.left,sum) + self.pathSum(root.right,sum)

     def pathSumWithRoot(self,root,sum):

         if root == None:

             return

         ret =

         if root.val == sum:

             ret +=

         ret += self.pathSumWithRoot(root.left,sum-root.val) + self.pathSumWithRoot(root.right,sum-root.val)

         return ret

 class Solution(object):

     def pathSum(self, root, target):

         # define global result and path

         self.result =

         cache = {:}

         # recursive to get result

         self.dfs(root, target, , cache)

         # return result

         return self.result

     def dfs(self, root, target, currPathSum, cache):

         # exit condition

         if root is None:

             return

         # calculate currPathSum and required oldPathSum

         currPathSum += root.val

         oldPathSum = currPathSum - target

         # update result and cache

         self.result += cache.get(oldPathSum, )

         cache[currPathSum] = cache.get(currPathSum, ) + 

         # dfs breakdown

         self.dfs(root.left, target, currPathSum, cache)

         self.dfs(root.right, target, currPathSum, cache)

         # when move to a different branch, the currPathSum is no longer available, hence remove one.

         cache[currPathSum] -=