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.