LeetCode 437. Path Sum III

Intuition

Maintain a Hashmap to store prefix_sum and: frequency

Base Case: pathSums[0] = 1 to handle the case when path from Root -> CurrentNode equals targetSum exactly

DFS Traversal

1. Add node.val to currSum
2. check if currSum - targetSum in hashmap if yes add that count to result
3. Add currSum to hashmap
4. recurse left and right
5. Before returning to the parent, remove the current' node's sum from hashmap to ensure the other branch doesn't see prefix sum from this branch

Optimal Solution

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        self.paths = 0
        self.pathSums = defaultdict(int)
        self.pathSums[0] = 1

        def dfs(r, currSum):
            if not r:
                return

            # update current sum
            currSum += r.val
            # check if we have complementary in dict
            if (currSum - targetSum) in self.pathSums:
                self.paths += self.pathSums[currSum - targetSum]
            self.pathSums[currSum] += 1

            dfs(r.right, currSum)
            dfs(r.left, currSum)

			# remove curr_Sum so other branch doesn't see
            self.pathSums[currSum] -= 1

        dfs(root,0)
        return self.paths

Time Complexity

O(N) Time Complexity

O(N) Space Complexity