437. Path Sum III

Problem Statement

link: LeetCode.cn LeetCode 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:

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

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

Solution Approach

The solution utilizes depth-first search (DFS) to traverse the binary tree while maintaining a dictionary to track cumulative sums along the paths. It counts the occurrences of sums that meet the target and returns the total count.

Algorithm

1. Perform a depth-first search (DFS) traversal of the binary tree.
2. Maintain a dictionary to record cumulative sums along the paths encountered during traversal.
3. Check for the difference between the current sum and the target at each node, adding the count of such differences found in the dictionary to the result.
4. Utilize backtracking to ensure accurate counting as traversal progresses through different branches of the tree.

Implement

    # 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:
          #prex      dif = curr - target check if dif in prex
          #{sub_sum: count} if dif == sub_sum   res += count
          def dfs(node, position, crr):
              if not node:
                  return 0
              crr += node.val
              dif = crr - targetSum 

              self.res += position.get(dif, 0)
              position[crr] += 1
              dfs(node.left, position, crr)
              dfs(node.right, position,crr)
              position[crr] -= 1  
              
          position = defaultdict(int)
          position[0] = 1
          self.res = 0
          dfs(root, position, 0)
          return self.res

                

    
    

Twitter  facebook  Email