437.Path_Sum_III(Medium).md

437. Path Sum III (Medium)

Date and Time: Nov 11, 2024, 21:52 (EST)

Link: https://leetcode.com/problems/path-sum-iii/

Question:

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8

Output: 3

Explanation: The paths that sum to 8 are shown.

Example 2:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

Output: 3

Constraints:

• The number of nodes in the tree is in the range [0, 1000].

• -10^9 <= Node.val <= 10^9

• -1000 <= targetSum <= 1000

Walk-through:

Non-optimized Solution:

Similar to Path Sum II and Path Sum, we run the algorithm on each node to find path sum until curSum == targetSum, we can increment res += 1.

Prefix Sum Solution:

Similar to 560.Subarray Sum Equals K, we build a hashmap{} to keep track of each curSum with their counts. When diff = curSum - targetSum exists in hashmap{}, that means we have ways to get the targetSum, so we update res += hashmap[diff].

Decrement hashmap[curSum] by 1 after we finished traversing node's left, right subtrees. Because we don't want other subtree to use the count of this prefixSum in our current subtree. For example, the left subtree has prefixSum {5: 1}, if we have a diff = 5 in right subtree, we should use this hashmap[5] from the left-subtree.

Intuitive Solution:

# 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: Optional[TreeNode], targetSum: int) -> int:
        # Start from each node to run DFS, if curSum for this node == targetSum, res += 1

        # TC: O(n^2), n is # nodes in the tree, SC: O(1)
        res = 0
        def findPath(node, curSum):
            nonlocal res
            if not node:
                return
            curSum += node.val
            if curSum == targetSum:
                res += 1
            findPath(node.left, curSum)
            findPath(node.right, curSum)

        def dfs(root):
            if not root:
                return
            findPath(root, 0)
            dfs(root.left)
            dfs(root.right)
        
        dfs(root)
        return res

Time Complexity: $O(n^2)$, n is number of nodes in the tree. Since we are runnig DFS on each node, and runnnig DFS again to find targetSum.
Space Complexity: $O(1)$

prefixSum Solution:

# 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: Optional[TreeNode], targetSum: int) -> int:
        # PrefixSum approach
        # Starting from root, maintain a hashmap with diff (curSum - targetSum)

        # hashmap = {0: 1, 10: 1, 15: 1, 16: 1, 18: 2, 20: 1}
        # 3 paths
        # 10 + 5 + 3 - 8 = 10
        # 10 + 5 + 2 + 1 - 8 = 10
        # 10 - 3 + 11 - 8 = 10
        # diff = 10, hashmap[10] = 1, res += 1, so res = 3

        # TC: O(n), n is # nodes in tree, SC: O(n)
        res = 0
        hashmap = {0: 1}
        def dfs(node, curSum):
            nonlocal res
            if not node:
                return
            curSum += node.val
            diff = curSum - targetSum
            res += hashmap.get(diff, 0)     # Update res with # ways for diff
            hashmap[curSum] = hashmap.get(curSum, 0) + 1      # Add curSum to hashmap
            dfs(node.left, curSum)
            dfs(node.right, curSum)
            hashmap[curSum] -= 1    # Keep only current subtree's prefixSum

        dfs(root, 0)
        return res

Time Complexity: $O(n)$, n is # nodes in the tree.
Space Complexity: $O(n)$

Same DFS, PrefixSum:

# 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: Optional[TreeNode], targetSum: int) -> int:
        # prefixSum for each subtree
        # maintain curSum, hashmap to keep track for each subtree only

        # TC: O(n), n is # nodes in tree, SC: O(n)
        curSum, res = 0, 0
        hashmap = {0: 1}
        def dfs(node):
            nonlocal curSum, res, hashmap
            if not node:
                return
            curSum += node.val
            diff = curSum - targetSum
            res += hashmap.get(diff, 0)
            # Update hashmap
            hashmap[curSum] = hashmap.get(curSum, 0) + 1
            dfs(node.left)
            dfs(node.right)
            # clean out for other subtree
            hashmap[curSum] -= 1
            curSum -= node.val

        dfs(root)
        return res