Path Sum II

class Solution {
public:
    void explorePaths(TreeNode* current, int targetSum, vector<int>& currentPath,
                     vector<vector<int>>& allPaths) {
        if (current == NULL) {
            return;
        }
        currentPath.push_back(current->val);
        if (targetSum == current->val && current->left == NULL &&
            current->right == NULL) {
            allPaths.push_back(vector<int>(currentPath));
        } else {
            explorePaths(current->left, targetSum - current->val, currentPath, allPaths);
            explorePaths(current->right, targetSum - current->val, currentPath, allPaths);
        }
        currentPath.pop_back();
    }
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> allPaths;
        vector<int> currentPath;
        explorePaths(root, sum, currentPath, allPaths);
        return allPaths;
    }
};

This code in C++ is designed to solve a problem where you have to find all root-to-leaf paths in a binary tree where each path's sum equals to a given number. This summary outlines how the solution is structured and executed using depth-first search (DFS):

• Define a function explorePaths that recursively explores each path in the tree.

  • This function takes the current node (TreeNode* current), the remaining sum (int targetSum), the path that has led to the current node (vector<int>& currentPath), and a container to store all valid paths (vector<vector<int>>& allPaths).
  • Add the current node's value to currentPath.
  • Check if the current node is a leaf and if the path sum equals the target sum; if so, add the current path to allPaths.
  • Continue the path exploration recursively for both left and right children of the current node.
  • Remove the last element from currentPath after exploring both subtrees to backtrack.

• The primary function pathSum initializes the necessary data structures and starts the recursive path exploration from the root.

  • It initializes allPaths to store all valid paths and currentPath to store the current path being explored.
  • Calls explorePaths starting from the root.

This approach ensures that you examine all potential paths from the root to each leaf, checking if the accumulated values form the desired sum, and backtrack to explore all possible configurations using DFS. This method efficiently collects all satisfying paths in a structured manner without revisiting or recalculating paths unnecessarily.

class Solution {
    private void helper(
        TreeNode currentNode,
        int targetSum,
        List<Integer> currentPath,
        List<List<Integer>> allPaths
    ) {
        if (currentNode == null) {
            return;
        }
    
        currentPath.add(currentNode.val);
    
        if (
            targetSum == currentNode.val && currentNode.left == null && currentNode.right == null
        ) {
            allPaths.add(new ArrayList<>(currentPath));
        } else {
            helper(
                    currentNode.left,
                    targetSum - currentNode.val,
                    currentPath,
                    allPaths
                );
            helper(
                    currentNode.right,
                    targetSum - currentNode.val,
                    currentPath,
                    allPaths
                );
        }
    
        currentPath.remove(currentPath.size() - 1);
    }
    
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> allPaths = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();
        helper(root, sum, currentPath, allPaths);
        return allPaths;
    }
}

In the provided Java solution for the problem "Path Sum II," the goal is to find all root-to-leaf paths in a binary tree where each path's sum equals a given target. The approach involves utilizing a recursive helper function to traverse the tree and accumulate paths meeting the criteria.

• The helper method is designed to:

  • Return immediately if the currentNode is null, indicating the end of a path.
  • Add the current node's value to currentPath, which tracks the nodes of the current path being examined.
  • Check if the current node is a leaf (both left and right children are null) and whether the sum of currentPath equals targetSum. If so, add a copy of currentPath to allPaths.
  • Recur on the left child, decreasing the targetSum by the current node's value.
  • Recur on the right child similarly.
  • Remove the last element from currentPath after visiting both children to backtrack.

• The pathSum method initializes structures to hold potential paths and calls helper using the root node. It then returns the list of valid paths.

This structure allows efficient path tracking and backtracking through the binary tree, dynamically adjusting to paths that meet the sum requirement, thus effectively solving the problem.

void findPathSum(TreeNode* node, int remainingSum, int* currentPath, int level,
                  int** sizes, int* pathCount, int*** paths) {
    if (node == NULL) return;
    currentPath[level] = node->val;
    if (node->left == NULL && node->right == NULL && remainingSum == node->val) {
        (*paths) = (int**)realloc((*paths), sizeof(int*) * (*pathCount + 1));
        (*paths)[*pathCount] = (int*)calloc(level + 1, sizeof(int));
        memcpy((*paths)[*pathCount], currentPath, sizeof(int) * (level + 1));
        (*sizes) = (int*)realloc((*sizes), sizeof(int) * (*pathCount + 1));
        (*sizes)[*pathCount] = level + 1;
        (*pathCount)++;
    }
    findPathSum(node->left, remainingSum - node->val, currentPath, level + 1, sizes,
           pathCount, paths);
    findPathSum(node->right, remainingSum - node->val, currentPath, level + 1, sizes,
           pathCount, paths);
}
int** computePathSums(TreeNode* nodeTree, int targetSum, int* numPaths,
                      int** colSizes) {
    int** allPaths = (int**)calloc(5000, sizeof(int*));
    int* pathBuffer = (int*)calloc(5000, sizeof(int));
    (*numPaths) = 0;
    (*colSizes) = (int*)calloc(5000, sizeof(int));
    findPathSum(nodeTree, targetSum, pathBuffer, 0, colSizes, numPaths, &allPaths);
    return allPaths;
}

The provided C code defines a solution for finding all root-to-leaf paths in a binary tree where each path's sum equals a given target sum. The solution utilizes depth-first search (DFS) to traverse the tree and backtracks to explore all possible paths. Here's a summary of the function structure and working:

• findPathSum: This function recursively traverses the tree from the root to each leaf. It updates the path and checks if the sum of the current path equals the target sum when it reaches a leaf node. If a path matches the given sum, it stores this valid path into a dynamically allocated array.

  • Receives the current node (node), the remaining sum to match (remainingSum), the path being currently built (currentPath), and the current depth in the tree (level).
  • If reaching a leaf node (both left and right children are NULL) and the remaining sum matches the node's value, the path is stored in an array that dynamically grows as more matching paths are found.
  • Recursively calls itself for the node's left and right children, adjusting the remaining sum and level as it goes deeper into the tree.

• computePathSums: This function prepares variables for the recursive search and initiates the tree traversal by calling findPathSum.

  • Initializes memory for path storage, setting up an array of path arrays (allPaths), a buffer to hold the current path (pathBuffer), and storage for path sizes (colSizes).
  • Adjusts and returns the allPaths containing all successful paths and their sizes through colSizes.

The code effectively handles memory management by reallocating arrays for paths and path sizes as needed. For each successful path, it ensures that the exact required memory is allocated, reducing waste. Moreover, the code cleanly separates the recursive traversal and path-check logic from the setup and memory management logic, enhancing readability and maintainability.

var calculatePaths = function (rootNode, targetSum) {
    let result = [];
    let currentPath = [];
    let findPaths = function (node, sumLeft, currentPath, result) {
        if (!node) {
            return;
        }
        currentPath.push(node.val);
        if (
            sumLeft === node.val &&
            !node.left &&
            !node.right
        ) {
            result.push([...currentPath]);
        } else {
            findPaths(
                node.left,
                sumLeft - node.val,
                currentPath,
                result,
            );
            findPaths(
                node.right,
                sumLeft - node.val,
                currentPath,
                result,
            );
        }
        currentPath.pop();
    };
    findPaths(rootNode, targetSum, currentPath, result);
    return result;
};

This JavaScript solution efficiently finds all paths in a binary tree where the sum of the node values equals a target sum. The function calculatePaths is designed to explore paths recursively from the root to the leaf nodes. Here’s how the function operates:

• Initialize result as an empty array to store paths that sum to the target.
• Begin with an empty currentPath array to keep track of the nodes along the current exploration path.
• Define an inner recursive function findPaths that:
  • Terminates if the current node is null.
  • Adds the current node's value to currentPath.
  • Checks if the remaining sum (after subtracting the current node's value) reaches zero and the current node is a leaf, i.e., it has no left or right child. If both conditions are met, a copy of currentPath is added to result.
  • Recursively calls itself for the left and right children of the current node, adjusting the sum left by subtracting the current node's value.
  • Removes the last element from currentPath after exploring both children to backtrack to the previous node.
• The initial call to findPaths passes the root node, the target sum, and the initialized arrays.

Return result which will contain all the valid paths that sum up to the given target. By leveraging recursion and backtracking, the solution efficiently explores all potential paths from root to leaf, ensuring the integrity of individual path exploration by managing the path state with currentPath manipulation.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
    
class Solution:
    def explorePaths(self, current, target, currentPath, allPaths):
        if not current:
            return
            
        currentPath.append(current.val)
            
        if current.val == target and current.left is None and current.right is None:
            allPaths.append(list(currentPath))
        else:
            self.explorePaths(current.left, target - current.val, currentPath, allPaths)
            self.explorePaths(current.right, target - current.val, currentPath, allPaths)
            
        currentPath.pop()
    
    def pathSum(self, root, sum):
        resultPaths = []
        self.explorePaths(root, sum, [], resultPaths)
        return resultPaths

This solution implements a method to find all paths in a binary tree where the sum of the values in the path is equal to a given target sum. The implementation uses Python and is divided into two main components: the TreeNode class which defines the structure of the tree nodes, and the Solution class which contains methods to explore potential paths and compute the desired output.

• TreeNode class:

  • Initializes a tree node with a value, x, and pointers to the left and right children, which are initially set to None.

• Solution class:

  • explorePaths function: It recursively explores all possible paths from a given node. Current path and its values are tracked in currentPath, while allPaths stores successful paths (paths whose values sum up to the target).

    • If the current node is None, the function returns immediately as this represents a non-existent node.
    • Current node's value is appended to currentPath.
    • If the current node's value equals the target and it is a leaf node (both children are None), a copy of currentPath is added to allPaths.
    • If not a leaf node or the value does not yet match target, the function explores further by subtracting the current node's value from target and recursing into both the left and right children.
    • After exploring both children, the last element is removed from currentPath to backtrack and explore new paths.

  • pathSum function: This function initializes the results list, resultPaths, and starts the path-finding process by calling explorePaths with the root of the tree, the target sum, an empty list for the current path, and an empty list for storing all valid paths.

  • Finally, the function returns resultPaths, which contains all paths that sum up to the given target value.

This approach is efficient since it involves backtracking to ensure that all potential paths are checked without redundantly processing the same paths multiple times. It utilizes both recursion and backtracking to explore all possible paths and manage path states, ensuring a complete search of the binary tree.