LeetCode: 113. Path Sum II

The Problem

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

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

Constraints:

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

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    vector<vector<int>> ans;
    vector<int> t;
    pathSumHelper( root, t, ans, targetSum, 0 );
    return ans;
}

void pathSumHelper( TreeNode *&root, 
	vector<int> &vec, vector<vector<int>> &ans,
	int &targetSum, int currentSum
) {
    if (root == NULL) return;

    int newSum = currentSum + root->val;

    vec.push_back(root->val);

    if( root->left == NULL && root->right == NULL ) {               
    	if( newSum == targetSum ) ans.push_back(vec);
	    vec.pop_back();
    	return;
    } else {
    	if(root->left != NULL)
    		pathSumHelper(root->left, vec, ans, targetSum, newSum);
    	if(root->right != NULL)
    		pathSumHelper(root->right, vec, ans, targetSum, newSum); 
    }
    vec.pop_back();
}

Here's a step-by-step explanation of the code:

1. vector<vector<int>> pathSum(TreeNode* root, int targetSum): This is the main function that you call to find all paths in the binary tree. It takes the root of the tree and the target sum as input and returns a 2D vector (vector<vector<int>>) containing all the paths.

2. Inside the pathSum function:

• vector<vector<int>> ans;: This vector will store the final result, i.e., all paths that match the target sum.
• vector<int> currentPath;: This is an empty vector used to temporarily store a path as it's being traversed.
• pathSumHelper(root, currentPath, ans, targetSum, 0);: It calls the helper function pathSumHelper to start the DFS traversal of the tree.

3. void pathSumHelper(TreeNode *&root, vector<int> &currentPath, vector<vector<int>> &ans, int &targetSum, int currentSum): This is the helper function that performs the DFS traversal and path sum calculation.

• TreeNode *&root: A reference to the current node being processed.
• vector<int> &currentPath: A reference to the vector used to store the current path.
• vector<vector<int>> &ans: A reference to the vector that stores the final result.
• int &targetSum: A reference to the target sum.
• int currentSum: The sum of values along the current path.

4. Inside the pathSumHelper function:

• if (root == NULL) return;: If the current node is NULL, it means the end of the path has been reached, so it returns.
• int newSum = currentSum + root->val;: Calculates the new sum by adding the current node's value to the sum of values along the path.
• currentPath.push_back(root->val);: Adds the current node's value to the path being constructed.
• if (root->left == NULL && root->right == NULL): Checks if the current node is a leaf node (i.e., it has no left or right children).
• If the current sum equals the target sum (newSum == targetSum), it means a valid path has been found, so it adds the path (stored in currentPath) to the ans vector.
• Then, it removes the last element from currentPath using currenPath.pop_back() to backtrack.
• If the current node is not a leaf node, it recursively calls pathSumHelper on its left and right children, passing the updated currentPath and newSum.

5. Finally, after the traversal is complete, the pathSum function returns the ans vector, which contains all the paths in the tree that match the target sum.