LC 0437 [M] Path Sum III - ALawliet/algorithms GitHub Wiki

2.1 High level walk through
In order to optimize from the brutal force solution, we will have to think of a clear way to memorize the intermediate result. Namely in the brutal force solution, we did a lot repeated calculation. For example 1->3->5, we calculated: 1, 1+3, 1+3+5, 3, 3+5, 5.
This is a classical 'space and time tradeoff': we can create a dictionary (named cache) which saves all the path sum (from root to current node) and their frequency.
Again, we traverse through the tree, at each node, we can get the currPathSum (from root to current node). If within this path, there is a valid solution, then there must be a oldPathSum such that currPathSum - oldPathSum = target.
We just need to add the frequency of the oldPathSum to the result.
During the DFS break down, we need to -1 in cache[currPathSum], because this path is not available in later traverse.
Check the graph below for easy visualization.

class Solution:
    def pathSum(self, root: TreeNode, target: int) -> int:        
        pre_sums = defaultdict(int, {0: 1})
        self.ans = 0
        
        def dfs(node, cursum):
            if not node: return

            cursum += node.val
            self.ans += pre_sums[cursum - target]

            pre_sums[cursum] += 1
            
            dfs(node.left, cursum)
            dfs(node.right, cursum)
            
            pre_sums[cursum] -= 1
        
        dfs(root, 0)
        return self.ans

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root, target):
        self.res = 0
        
        # store the addend/diff of oldPathSum to its count, similar idea to 2Sum
        self.cache = {} 
        
        def dfs(root, currPathSum):
            if not root: return None
            
            currPathSum += root.val

            if currPathSum == target:
                self.res += 1

            oldPathSum = currPathSum - target 
            if oldPathSum in self.cache:
                self.res += self.cache[oldPathSum]

            if currPathSum in self.cache:
                self.cache[currPathSum] +=1
            else:
                self.cache[currPathSum] = 1

            dfs(root.left, currPathSum)
            dfs(root.right, currPathSum)

            self.cache[currPathSum] -=1 # undo
        
        dfs(root, 0)
        
        return self.res