Python solution with detailed explanation
Path Sum III https://leetcode.com/problems/path-sum-iii/\n\nBrute Force Solution\n The simplest solution is to traverse each node (preorder traversal) and then 
**Path Sum III** https://leetcode.com/problems/path-sum-iii/\n\n**Brute Force Solution**\n* The simplest solution is to traverse each node (preorder traversal) and then find all paths which sum to the target using this node as root.\n* The worst case complexity for this method is N^2. \n* If we have a balanced tree, we have the recurrence: T(N) = N + 2T(N/2). This is the merge sort recurrence and suggests NlgN.\n```\nclass SolutionBruteForce(object):\n    def find_paths(self, root, target):\n        if root:\n            return int(root.val == target) + self.find_paths(root.left, target-root.val) + self.find_paths(root.right, target-root.val)\n        return 0\n\n    def pathSum(self, root, sum):\n        """\n        :type root: TreeNode\n        :type sum: int\n        :rtype: int\n        """\n        if root:\n            return self.find_paths(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)\n        return 0\n```\n\n**Two Sum Method: Optimized Solution**\n\n* A more efficient implementation uses the Two Sum idea. It uses a hash table (extra memory of order N). With more space, it gives us an O(N) complexity.\n* As we traverse down the tree, at an arbitrary node N, we store the sum until this node N (sum_so_far (prefix) + N.val). in hash-table.  Note this sum is the sum from root to N.\n* Now at a grand-child of N, say G, we can compute the sum from the root until G since we have the prefix_sum until this grandchild available.We pass in our recursive routine.\n* How do we know if we have a path of target sum which ends at this grand-child G? Say there are multiple such paths that end at G and say they start at A, B, C where A,B,C are predecessors of G. Then sum(root->G) - sum(root->A) = target. Similarly sum(root->G)-sum(root>B) = target. Therefore we can compute the complement at G as sum_so_far+G.val-target and look up the hash-table for the number of paths which had this sum\n* Now after we are done with a node and all its grandchildren, we remove it from the hash-table. This makes sure that the number of complement paths returned always correspond to paths that ended at a predecessor node.\n```\nclass Solution(object):\n    def helper(self, root, target, so_far, cache):\n        if root:\n            complement = so_far + root.val - target\n            if complement in cache:\n                self.result += cache[complement]\n            cache.setdefault(so_far+root.val, 0)\n            cache[so_far+root.val] += 1\n            self.helper(root.left, target, so_far+root.val, cache)\n            self.helper(root.right, target, so_far+root.val, cache)\n            cache[so_far+root.val] -= 1\n        return\n\n    def pathSum(self, root, sum):\n        """\n        :type root: TreeNode\n        :type sum: int\n        :rtype: int\n        """\n        self.result = 0\n        self.helper(root, sum, 0, {0:1})\n        return self.result\n```
[]