Python solution
DFS with memoization: Use a variable prevSum to record the sum of all node values from the root r to the parent p of the current node. Then including the curren
DFS with memoization: Use a variable `prevSum` to record the sum of all node values from the root `r` to the parent `p` of the current node. Then including the current node, the sum becomes `currSum = prevSum + node.val`. Now for each node on the path, we can calculate their respective `currSum`, we use a dictionary `rec` to record the frequency of all such sums. If the sum of nodes on a path ending with the current node has value `sum`, it implies that `currSum - sum` is in `rec`. Moreover, the number of such paths is `rec[currSum - sum]`. Then we can do DFS on the left and right child of the current node, with `currSum` being their `prevSum`. Also note that we need to do `rec[currSum] -= 1` after DFS on the left and right child of the current node, because the current node is not on the path of DFSs on other nodes, hence `currSum` is not available for other DFSs.\n \n Time complexity: `O(n)`, space complexity: `O(n)`.\n \n```\nclass Solution(object):\n    def pathSum(self, root, sum):\n        """\n        :type root: TreeNode\n        :type sum: int\n        :rtype: int\n        """\n        \n        def dfs(root, prevSum, sum):\n            if not root:\n                return \n            currSum = prevSum + root.val\n            if currSum - sum in rec:\n                self.count += rec[currSum - sum]\n            if currSum in rec:\n                rec[currSum] += 1\n            else:\n                rec[currSum] = 1\n            dfs(root.left, currSum, sum)\n            dfs(root.right, currSum, sum)\n            rec[currSum] -= 1\n            \n        self.count = 0\n        rec = {0:1}\n        dfs(root, 0, sum)\n        return self.count\n```\n\nSlightly better solution without the variable `self.count`:\n```\nclass Solution(object):\n    def pathSum(self, root, sum):\n        """\n        :type root: TreeNode\n        :type sum: int\n        :rtype: int\n        """\n        \n        def dfs(root, prevSum, sum):\n            if not root:\n                return 0\n            count = 0\n            currSum = prevSum + root.val\n            if currSum - sum in rec:\n                count += rec[currSum - sum]\n            if currSum in rec:\n                rec[currSum] += 1\n            else:\n                rec[currSum] = 1\n            count += dfs(root.left, currSum, sum)\n            count += dfs(root.right, currSum, sum)\n            rec[currSum] -= 1\n            return count\n            \n        rec = {0:1}\n        return dfs(root, 0, sum)\n```
[]