Python step-by-step walk through. Easy to understand. Two solutions comparison. : )
1. Brute Force: O(nlogn) ~ O(n^2)\n## 1.1 High level walk-through: \n1. (Define return) Define a global var: self.numOfPaths in the main function.\n2. (1st laye
# 1. Brute Force: O(nlogn) ~ O(n^2)\n## 1.1 High level walk-through: \n1. (Define return) Define a global var: `self.numOfPaths` in the main function.\n2. (1st layer DFS) Use recursive traverse to go through each `node` (can be **any order**: pre, in, post all fine).\n3. (2nd layer DFS) For each `node`, walk all paths. If a path sum equals to the `target`: `self.numOfPaths += 1`\n4. Return result:  `return self.numOfPaths` \n## 1.2 Complexity analysis\n### 1.2.1 Space \n1. Space complexity is O(1), due to there is no extra cache. However, for **any recursive** question, we need to think about **stack overflow**, namely the recursion should not go too deep. \n2. Assume we have **n** TreeNodes in total, the tree height will vary from **O(n)** (single sided tree) to **O(logn)**(balanced tree). \n3. The two DFS will go as deep as the tree height.\n### 1.2.2 Time\n1. Time complexity depends on the two DFS.\n2. 1st layer DFS will always take **O(n)**, due to here we will take each node out, there are in total **n** TreeNodes\n3. 2nd layer DFS will take range from **O(n)** (single sided tree) to **O(logn)**(balanced tree). This is due to here we are get all the paths from a given node. The length of path is proportional to the tree height.\n4. Therefore, the total time complexity is **O(nlogn)** to **O(n^2)**.\n## 1.3 Code\n```\nclass Solution(object):\n    def pathSum(self, root, target):\n        """\n        :type root: TreeNode\n        :type sum: int\n        :rtype: int\n        """\n        # define global return var\n        self.numOfPaths = 0\n        # 1st layer DFS to go through each node\n        self.dfs(root, target)\n        # return result\n        return self.numOfPaths\n    \n    # define: traverse through the tree, at each treenode, call another DFS to test if a path sum include the answer\n    def dfs(self, node, target):\n        # exit condition\n        if node is None:\n            return \n        # dfs break down \n        self.test(node, target) # you can move the line to any order, here is pre-order\n        self.dfs(node.left, target)\n        self.dfs(node.right, target)\n        \n    # define: for a given node, DFS to find any path that sum == target, if find self.numOfPaths += 1\n    def test(self, node, target):\n        # exit condition\n        if node is None:\n            return\n        if node.val == target:\n            self.numOfPaths += 1\n            \n        # test break down\n        self.test(node.left, target-node.val)\n        self.test(node.right, target-node.val)\n```\n\n# 2. Memorization of path sum: O(n)\n## 2.1 High level walk through\n1. In order to optimize from the brutal force solution, we will have to think of a clear way to memorize the intermediate result. Namely in the brutal force solution, we did a lot repeated calculation. For example `1->3->5`, we calculated: 1, 1+3, 1+3+5, 3, 3+5, 5. \n2. This is a classical \'space and time tradeoff\': we can create a dictionary (named `cache`) which saves all the path sum (from root to current node) and their frequency.\n3. Again, we traverse through the tree, at each node, we can get the `currPathSum` (from root to current node). If within this path, there is a valid solution, then there must be a `oldPathSum` such that `currPathSum - oldPathSum = target`. \n4. We just need to add the frequency of the `oldPathSum` to the result. \n5. During the DFS break down, we need to -1 in  `cache[currPathSum]`, because this path is not available in later traverse. \n6. Check the graph below for easy visualization. \n![image](https://s3-lc-upload.s3.amazonaws.com/users/wonderlives/image_1529701359.png)\n\n## 2.2 Complexity analysis:\n### 2.2.1 Space complexity\nO(n) extra space\n### 2.2.1 Time complexity\nO(n) as we just traverse once\n\n## 2.3 Code:\n```\nclass Solution(object):\n    def pathSum(self, root, target):\n        # define global result and path\n        self.result = 0\n        cache = {0:1}\n        \n        # recursive to get result\n        self.dfs(root, target, 0, cache)\n        \n        # return result\n        return self.result\n    \n    def dfs(self, root, target, currPathSum, cache):\n        # exit condition\n        if root is None:\n            return  \n        # calculate currPathSum and required oldPathSum\n        currPathSum += root.val\n        oldPathSum = currPathSum - target\n        # update result and cache\n        self.result += cache.get(oldPathSum, 0)\n        cache[currPathSum] = cache.get(currPathSum, 0) + 1\n        \n        # dfs breakdown\n        self.dfs(root.left, target, currPathSum, cache)\n        self.dfs(root.right, target, currPathSum, cache)\n        # when move to a different branch, the currPathSum is no longer available, hence remove one. \n        cache[currPathSum] -= 1\n```\n\t\t
[]