113. Path Sum II

Description

The problem is to find all root-to-leaf paths in a binary tree where the sum of the node values equals a given targetSum. Each path should be returned as a list of node values, and all such paths should be collected in a list of lists.

Intuition

To solve this problem, we can use a depth-first search (DFS) approach. The idea is to explore every possible path from the root to the leaf nodes, keeping track of the cumulative sum of node values along the way. If a path's sum equals the targetSum and it ends at a leaf node, it is a valid path that should be included in the result.

Approach

1. Base Case: - If the tree is empty (i.e., root is null), return an empty list.
2. Depth-First Search (DFS): - Use a recursive function to traverse the tree. Start from the root node and explore each path by visiting left and right subtrees. - Maintain a running sum of node values (currentSum) and a list of nodes (path) representing the current path from the root. - At each node: - Add the node's value to currentSum and include it in path. - Check if currentSum equals targetSum and if the current node is a leaf (i.e., it has no children). If both conditions are met, add the current path to the result list. - Recursively explore the left and right subtrees. - After exploring a node's children, remove the node from path (backtracking) to allow other paths to be explored.
3. Return Result: - Once all paths have been explored, return the list of valid paths.

Complexity

Time Complexity:

The time complexity is (O(n)), where n is the number of nodes in the tree. In the worst case, every node is visited once during the DFS.

Space Complexity:

The space complexity is (O(h)), where h is the height of the tree. This is the space used by the recursion stack during DFS. In the worst case, the space complexity could be (O(n)) if the tree is skewed.

Code

C++

class Solution {
public:
    vector> pathSum(TreeNode* root, int targetSum) {
        vector> result;
        vector path;
        
        function rec = [&](TreeNode* node, int sum) {
            if (!node) return;

            sum += node->val;
            path.push_back(node->val);

            if (sum == targetSum && !node->left && !node->right) {
                result.push_back(path);
            } else {
                rec(node->left, sum);
                rec(node->right, sum);
            }

            path.pop_back();
        };

        rec(root, 0);
        return result;
    }
};

Python

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if not root:
            return []

        result = []

        def rec(node, currentSum, path):
            if not node:
                return

            currentSum += node.val
            path.append(node.val)

            if currentSum == targetSum and not node.left and not node.right:
                result.append(list(path))
            else:
                rec(node.left, currentSum, path)
                rec(node.right, currentSum, path)

            path.pop()

        rec(root, 0, [])
        return result

Java

class Solution {
    public List> pathSum(TreeNode root, int targetSum) {
        List> result = new ArrayList<>();
        List path = new ArrayList<>();

        helper(root, targetSum, 0, path, result);
        return result;
    }

    private void helper(TreeNode node, int targetSum, int sum, List path, List> result) {
        if (node == null) return;

        sum += node.val;
        path.add(node.val);

        if (sum == targetSum && node.left == null && node.right == null) {
            result.add(new ArrayList<>(path));
        } else {
            helper(node.left, targetSum, sum, path, result);
            helper(node.right, targetSum, sum, path, result);
        }

        path.remove(path.size() - 1);
    }
}

JavaScript

var pathSum = function (root, targetSum) {
    if (!root) return [];
    const r = [];
    const rec = (node, sum, path) => {
        if (!node) return;
        const s = sum + node.val;
        const p = [...path, node.val];
        console.log(s)
        if (s === targetSum && !node.left && !node.right) {
            r.push(p);
            return;
        }

        rec(node.left, s, p);
        rec(node.right, s, p);
    }

    rec(root, 0, []);
    return r;
};