[Leetode] 437. Path Sum III

https://leetcode.com/problems/path-sum-iii/description/?envType=study-plan-v2&envId=leetcode-75

initial

My initial solution only counted the paths from the root.

    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def dfs(node, targetSum, curSum):
            if node is None:
                return
            # curSum += node.val  # Add current node's value to the sum
            if curSum == targetSum:
                self.ans += 1

            # Recursively explore left and right subtrees
            if node.left:
                dfs(node.left, targetSum, curSum+node.left.val)
            if node.right:
                dfs(node.right, targetSum, curSum+node.right.val)

        # Start DFS from root
        dfs(root, targetSum, root.val)
        return self.ans

solution (time inefficient)

actually we need to perform the same logic onto root's left and right and all the nodes.

class Solution:
    def __init__(self):
        self.ans = 0

    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def dfs(node,targetSum,curSum):
            if node is None:
                return
            curSum+=node.val
            if curSum==targetSum:
                self.ans+=1
            dfs(node.left,targetSum,curSum)
            dfs(node.right,targetSum,curSum)
        def traverse(node):
            if node is None:
                return
            # Start DFS from the current node
            dfs(node, targetSum, 0)
            # Recursively traverse left and right subtrees
            traverse(node.left)
            traverse(node.right)

        # Start the traversal from the root
        traverse(root)
        return self.ans

prefix sum with hashmap solution (better)

in the hashmap, we store the freq of old path sum. If
current path sum - old path sum stored in dictionary equals the targetSum, this means that there is a valid path from some ancestor node to the current node whose path equals the target sum.

In which case, we add that freq.
Rmb to backtrack the old path sum by subtracting the frequency of that old path sum.

from collections import defaultdict

class Solution:
    def __init__(self):
        self.result = 0
        self.prefix_sum = defaultdict(int)  # Dictionary to store prefix sum frequencies

    def pathSum(self, root, targetSum):
        # Start DFS traversal from the root node with initial current sum = 0
        self.prefix_sum[0] = 1  # Base case: to handle when the path itself sums to target
        self.dfs(root, 0, targetSum)  # Start DFS from root with initial sum = 0
        return self.result  # Return the final result

    def dfs(self, node, current_sum, targetSum):
        if not node:
            return
        
        # Add current node's value to the running sum
        current_sum += node.val
        
        # Check if there is a prefix sum that makes the current sum - target sum
        if current_sum - targetSum in self.prefix_sum:
            # If it exists, it means we've found a valid path
            self.result += self.prefix_sum[current_sum - targetSum]
        
        # Add the current sum to the hashmap (frequency of sums)
        self.prefix_sum[current_sum] += 1
        
        # Recursively visit the left and right children
        self.dfs(node.left, current_sum, targetSum)
        self.dfs(node.right, current_sum, targetSum)
        
        # Backtrack: remove the current sum from the hashmap
        self.prefix_sum[current_sum] -= 1

complexity

for brute force, time is n^2 cuz it grows exponentially by the number of nodes cuz we are doing dfs on the child notes too. Space is o(h)

but for prefix time is o(n) cuz each node is visited only once. space is o(h)