Скачать или смотреть 🚀 Path Sum III | Optimized Solution | Prefix Sum + HashMap | LeetCode 75 🔥

In this problem, we need to find the number of paths in a binary tree where the sum of values along the path equals targetSum. The path can start from any node and end at any node, but it must move downwards (parent to child only).

🔹 Approach 2: Optimized Solution (Prefix Sum + HashMap)

Instead of checking all possible paths individually (which takes O(N²) in the worst case), we use a Prefix Sum with a HashMap to store cumulative sums. This allows us to check if a valid path sum exists in O(N) time.

📌 Steps to Solve:

1️⃣ Use DFS traversal to explore the tree while maintaining a running sum (currentSum).
2️⃣ Store currentSum in a hashmap to track how many times it has occurred.
3️⃣ Check if there is a previous prefix sum that equals currentSum - targetSum, meaning a valid path exists.
4️⃣ Recursively continue for left and right subtrees, updating the hashmap accordingly.
5️⃣ Before returning from a node, remove its prefix sum from the hashmap to ensure we only count paths in the current branch.

✅ Python Code (Optimized DFS + HashMap)

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Solution:
def dfs(self, node, targetSum, currentSum, prefixSum):
if not node:
return 0

Update current sum
currentSum += node.val
count = prefixSum.get(currentSum - targetSum, 0) # Check if valid path exists

Store current sum in hashmap
prefixSum[currentSum] = prefixSum.get(currentSum, 0) + 1

Recur for left and right subtrees
count += self.dfs(node.left, targetSum, currentSum, prefixSum)
count += self.dfs(node.right, targetSum, currentSum, prefixSum)

Remove current sum from hashmap (backtracking)
prefixSum[currentSum] -= 1

return count

def pathSum(self, root, targetSum):
prefixSum = {0: 1} # Base case: a path sum that starts from root
return self.dfs(root, targetSum, 0, prefixSum)

🔹 Time Complexity: O(N), since we visit each node only once.
🔹 Space Complexity: O(H), where H is the height of the tree (for recursion and hashmap storage).

📢 This optimized DFS with Prefix Sum significantly improves performance, making it feasible for large trees (up to 10⁵ nodes).