_437. Path Sum III.md

437. Path Sum III

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 03, 2024

Last updated : July 03, 2024

---

Related Topics : Tree, Depth-First Search, Binary Tree

Acceptance Rate : 46.04 %

---

Version 2 is much more efficient due to the lack of overhead from generating $n$ counters. In V2, the solution is still $O(n)$ but it's much much much more efficient.

---

Solutions

• m437 v1 Summation of Counters.py
• m437 v2 Shared Prefix Sum.py

Python

m437 v1 Summation of Counters.py

# 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:
        if not root :
            return 0
        self.output = 0

        # Sums dict is a counter
        def dfs(curr: Optional[TreeNode], currSum: int) -> Counter :
            valNeeded = currSum + targetSum
            currSum += curr.val
            
            output = Counter()
            if curr.left :
                output += dfs(curr.left, currSum)
            if curr.right :
                output += dfs(curr.right, currSum)
            output[currSum] += 1

            self.output += output.get(valNeeded, 0)

            return output
        
        dfs(root, 0)
        return self.output

m437 v2 Shared Prefix Sum.py

# 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:
        if not root :
            return 0

        prefixSum = {}
        self.output = 0

        # Sums dict is a counter
        def dfs(curr: Optional[TreeNode], currSum: int) -> None :
            prefixSum[currSum] = prefixSum.get(currSum, 0) + 1
            valNeeded = currSum + curr.val - targetSum
            self.output += prefixSum.get(valNeeded, 0)

            if curr.left :
                dfs(curr.left, currSum + curr.val)
            if curr.right :
                dfs(curr.right, currSum + curr.val)

            prefixSum[currSum] -= 1

        dfs(root, 0)
        return self.output