# Time:  O(n^2)
# Space: O(h)

# You are given a binary tree in which each node contains an integer value.
#
# Find the number of paths that sum to a given value.
#
# The path does not need to start or end at the root or a leaf, 
# but it must go downwards (traveling only from parent nodes to child nodes).
#
# The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
#
# Example:
#
# root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
#
#       10
#      /  \
#     5   -3
#   / \    \
#   3   2   11
#  / \   \
# 3  -2   1
#
# Return 3. The paths that sum to 8 are:
#
# 1.  5 -> 3
# 2.  5 -> 2 -> 1
# 3. -3 -> 11

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        def pathSumHelper(root, prev, sum):
            if not root:
                return 0

            curr = prev + root.val;
            return int(curr == sum) + \
                   pathSumHelper(root.left, curr, sum) + \
                   pathSumHelper(root.right, curr, sum)

        if not root:
            return 0

        return pathSumHelper(root, 0, sum) + \
               self.pathSum(root.left, sum) + \
               self.pathSum(root.right, sum)

@@ -9,10 +9,8 @@
  O(n
-%5E2
 )%0A# 
@@ -18,17 +18,17 @@
 pace: O(
-h
+n
 )%0A%0A# You
@@ -820,22 +820,900 @@
 ne%0A%0A
-class Solution
+# Time:  O(n)%0A# Space: O(n)%0A%0A# Definition for a binary tree node.%0A# class TreeNode(object):%0A#     def __init__(self, x):%0A#         self.val = x%0A#         self.left = None%0A#         self.right = None%0A%0Aclass Solution(object):%0A    def pathSum(self, root, sum):%0A        %22%22%22%0A        :type root: TreeNode%0A        :type sum: int%0A        :rtype: int%0A        %22%22%22%0A        def helper(root, cur, sum, lookup):%0A            if root is None:%0A                return 0%0A            cur += root.val%0A            result = lookup%5Bcur - sum%5D%0A            lookup%5Bcur%5D += 1%0A            result += helper(root.left, cur, sum, lookup) + %5C%0A                      helper(root.right, cur, sum, lookup)%0A            lookup%5Bcur%5D -= 1%0A            return result%0A        %0A        lookup = collections.defaultdict(int)%0A        lookup%5B0%5D = 1%0A        return helper(root, 0, sum, lookup)%0A%0A%0A# Time:  O(n%5E2)%0A# Space: O(h)%0Aclass Solution2
 (obj

Update path-sum-iii.py