113. Path Sum II

Problem Statement

link: https://leetcode.com/problems/path-sum-ii/ https://leetcode.cn/problems/path-sum-ii/

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Example:

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

Input: root = [1,2,3], targetSum = 5 Output: []

Input: root = [1,2], targetSum = 0 Output: []

Solution Approach

The solution employs a depth-first search (DFS) combined with backtracking to explore all root-to-leaf paths and find the ones that sum up to the target.

Algorithm

1. DFS and Path Maintenance: Initiate DFS from the root node, maintaining a running sum and a current path list, updated at each visited node.
2. Leaf Node Check: Upon reaching a leaf node, if the running sum matches the target sum, append a deep copy of the current path to the results.
3. Backtracking: After visiting left and right subtrees of a node, backtrack by removing the node from the current path and continue to explore other branches.

Implement

    class Solution:
  def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
      res = []
      path = []
      def dfs(node, tSum):
          if not node:
              return
          path.append(node.val)
          tSum -= node.val
          if not node.left and not node.right and tSum == 0:
              res.append(path[:]) # backtracking must use the deep copy
          dfs(node.left, tSum)
          dfs(node.right, tSum)
          path.pop()

      dfs(root, targetSum)
      return res

    
    

Twitter  facebook  Email