{x}
blog image

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 1:

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]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Example 2:

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

Example 3:

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

 

Constraints:

  • The number of nodes in the tree is in the range [0, 5000].
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

113. Path Sum II

Problem Description

Given the root of a binary tree and an integer targetSum, find all root-to-leaf paths where the sum of node values equals targetSum. Return each path as a list of node values.

Solution: Depth-First Search (DFS)

This problem is best solved using Depth-First Search (DFS). DFS explores a tree by going as deep as possible along each branch before backtracking. We'll use a recursive approach to explore all paths.

Algorithm:

  1. Base Case: If the current node is null, return.
  2. Update Sum: Subtract the current node's value from targetSum.
  3. Append to Path: Add the current node's value to the current path.
  4. Leaf Node Check: If it's a leaf node (no left or right children) and the updated targetSum is 0, add the current path to the result.
  5. Recursive Calls: Recursively call the function for the left and right children.
  6. Backtrack: After processing the left and right children, remove the current node's value from the path (backtracking) to explore other paths.

Time and Space Complexity Analysis

  • Time Complexity: O(N), where N is the number of nodes in the tree. In the worst case, we visit each node once.
  • Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be N. Additionally, we use O(H) space to store the path in the recursive calls.

Code Implementation (Python)

# 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: TreeNode, targetSum: int) -> List[List[int]]:
        result = []
        path = []
 
        def dfs(node, current_sum):
            if not node:
                return
 
            current_sum -= node.val
            path.append(node.val)
 
            if not node.left and not node.right and current_sum == 0:
                result.append(path.copy())
 
            dfs(node.left, current_sum)
            dfs(node.right, current_sum)
 
            path.pop()  # Backtrack
 
        dfs(root, targetSum)
        return result

Code Implementation (Java)

import java.util.*;
 
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
 
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return result;
    }
 
    private void dfs(TreeNode node, int currentSum) {
        if (node == null) {
            return;
        }
 
        currentSum -= node.val;
        path.add(node.val);
 
        if (node.left == null && node.right == null && currentSum == 0) {
            result.add(new ArrayList<>(path));
        }
 
        dfs(node.left, currentSum);
        dfs(node.right, currentSum);
 
        path.remove(path.size() - 1); // Backtrack
    }
}

(Other languages like C++, Go, JavaScript, and Rust would follow a very similar structure, adapting the syntax and data structures to the specific language.)

This DFS solution efficiently finds all root-to-leaf paths with the target sum, offering a clear and concise approach to solving the problem. The backtracking step is crucial for correctly exploring all possible paths.