https://leetcode.com/problems/path-sum-iii/#/description

# naive solution
# O(N^2)
class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        self.count = 0
        self.dfs(root, sum)
        self.arr = []
        return self.count

    def dfs(self, root, sum):
        if root:
            self.helper(root, sum)
            self.dfs(root.left, sum)
            self.dfs(root.right, sum)

    def helper(self, root, target):
        if root:
            if target == root.val:
                self.count += 1
            self.helper(root.left, target - root.val)
            self.helper(root.right, target - root.val)

# similar to prefix sum array
# O(N)
class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        self.count = 0
        self.pre_sum = {0: 1}
        self.helper(root, sum, 0)
        return self.count

    def helper(self, root, target, curr_sum):
        if not root:
            return
        curr_sum += root.val
        if curr_sum - target in self.pre_sum:
            self.count += self.pre_sum[curr_sum - target]

        self.pre_sum[curr_sum] = self.pre_sum.get(curr_sum, 0) + 1
        self.helper(root.left, target, curr_sum)
        self.helper(root.right, target, curr_sum)
        self.pre_sum[curr_sum] -= 1

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        self.pre_sum = {0: 1}
        res = self.helper(root, sum, 0)
        return res

    def helper(self, root, target, curr_sum):
        if not root:
            return 0
        curr_sum += root.val
        res = self.pre_sum.get(curr_sum - target, 0)

        self.pre_sum[curr_sum] = self.pre_sum.get(curr_sum, 0) + 1
        res += self.helper(root.left, target, curr_sum)
        res += self.helper(root.right, target, curr_sum)
        self.pre_sum[curr_sum] = self.pre_sum[curr_sum] - 1
        return res

e437: path sum 3
e112: path sum 1