Path Sum 2

Problem Statement:

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

Solution:

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        pathSum(root, targetSum, new ArrayList<Integer>(), res);
        return res;
    }
    
    void pathSum(TreeNode root, int targetSum, List<Integer> sol, List<List<Integer>> res) {
        if (root == null) {
            return;
        }
        
        targetSum = targetSum - root.val;
        sol.add(root.val);
        
        if (root.left == null && root.right == null && targetSum == 0) {
            res.add(new ArrayList<>(sol));
            return;
        }
        
        pathSum(root.left, targetSum, new ArrayList<>(sol), res);
        pathSum(root.right, targetSum, new ArrayList<>(sol), res);
    }
}