Description:
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.
Examples:
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
Example 2:
Input: root = [1,2,3], targetSum = 5
Output: []
Example 3:
Input: root = [1,2], targetSum = 0
Output: []Solution in Python:
To solve the problem of finding all root-to-leaf paths where the sum of node values equals the target sum in a binary tree, we can use a Depth-First Search (DFS) approach.
Python
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
# This list will hold all the paths that sum up to targetSum
all_paths = []
# Helper function to perform DFS on the tree
def dfs(node, current_path, current_sum):
if not node:
return
# Add the current node's value to the path and update the current sum
current_path.append(node.val)
current_sum += node.val
# If the current node is a leaf and its path sums up to targetSum, add the path to all_paths
if not node.left and not node.right and current_sum == targetSum:
all_paths.append(list(current_path))
else:
# Recur on the left and right subtrees
dfs(node.left, current_path, current_sum)
dfs(node.right, current_path, current_sum)
# Backtrack by removing the current node's value from the path
current_path.pop()
# Start DFS with an empty path and a sum of 0
dfs(root, [], 0)
return all_pathsDetailed Comments:
- TreeNode Class Definition:
- The
TreeNodeclass defines the structure of a node in a binary tree. - Each node has an integer value (
val), a left child (left), and a right child (right).
- The
- pathSum Method:
- Input Parameters: The method takes two parameters:
root, which is the root of the binary tree, andtargetSum, which is the target sum we are looking for in the root-to-leaf paths. - The method initializes an empty list
all_pathsthat will store all the valid paths.
- Input Parameters: The method takes two parameters:
- dfs Helper Function:
- Parameters: This function takes three parameters: the current
node, the current path (current_path), and the current sum (current_sum). - Base Case: If the current
nodeisnull, we return immediately. - Update Path and Sum: We add the current node’s value to
current_pathand updatecurrent_sumwith the node’s value. - Leaf Node Check: If the current node is a leaf (i.e., it has no left or right children) and the
current_sumequalstargetSum, we add a copy ofcurrent_pathtoall_paths. - Recursive Calls: We recursively call
dfson the left and right children of the current node. - Backtracking: After exploring both subtrees, we backtrack by removing the current node’s value from
current_pathto explore other potential paths.
- Parameters: This function takes three parameters: the current
- Returning the Result:
- The
pathSummethod starts the DFS by callingdfswith the root node, an empty path, and an initial sum of 0. - Finally, it returns the
all_pathslist containing all the paths that sum to the target sum.
- The
This approach ensures that all root-to-leaf paths are explored, and only those paths that meet the target sum are collected and returned. The time complexity is O(n), where nnn is the number of nodes in the tree, as each node is visited once. The space complexity is O(h), where hhh is the height of the tree, representing the maximum depth of the recursion stack and the maximum path length stored.
Solution in Javascript:
JavaScript
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {number[][]}
*/
var pathSum = function(root, targetSum) {
// This array will hold all the paths that sum up to targetSum
const allPaths = [];
/**
* Helper function to perform DFS on the tree
* @param {TreeNode} node - the current node
* @param {number[]} currentPath - the current path from the root to this node
* @param {number} currentSum - the sum of the values in currentPath
*/
function dfs(node, currentPath, currentSum) {
if (!node) {
return;
}
// Add the current node's value to the path and update the current sum
currentPath.push(node.val);
currentSum += node.val;
// If the current node is a leaf and its path sums up to targetSum, add the path to allPaths
if (!node.left && !node.right && currentSum === targetSum) {
allPaths.push([...currentPath]);
} else {
// Recur on the left and right subtrees
dfs(node.left, currentPath, currentSum);
dfs(node.right, currentPath, currentSum);
}
// Backtrack by removing the current node's value from the path
currentPath.pop();
}
// Start DFS with an empty path and a sum of 0
dfs(root, [], 0);
return allPaths;
};Solution in Java:
Java
import java.util.*;
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> allPaths = new ArrayList<>();
List<Integer> currentPath = new ArrayList<>();
dfs(root, targetSum, currentPath, allPaths);
return allPaths;
}
/**
* Helper method to perform DFS and find all root-to-leaf paths
* @param node Current node in traversal
* @param remainingSum Remaining sum to achieve targetSum
* @param currentPath Current path from root to current node
* @param allPaths List to collect all paths that sum to targetSum
*/
private void dfs(TreeNode node, int remainingSum, List<Integer> currentPath, List<List<Integer>> allPaths) {
if (node == null) {
return;
}
// Add current node to the path
currentPath.add(node.val);
// Check if this is a leaf node and if the current path sums up to targetSum
if (node.left == null && node.right == null && node.val == remainingSum) {
// Add a copy of currentPath to allPaths (Java passes references, so we need to create a copy)
allPaths.add(new ArrayList<>(currentPath));
} else {
// Recur on the left subtree
dfs(node.left, remainingSum - node.val, currentPath, allPaths);
// Recur on the right subtree
dfs(node.right, remainingSum - node.val, currentPath, allPaths);
}
// Backtrack: Remove current node from currentPath to explore other paths
currentPath.remove(currentPath.size() - 1);
}
}Solution in C#:
C#
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> PathSum(TreeNode root, int targetSum) {
List<IList<int>> allPaths = new List<IList<int>>();
List<int> currentPath = new List<int>();
Dfs(root, targetSum, currentPath, allPaths);
return allPaths;
}
/**
* Helper method to perform DFS and find all root-to-leaf paths
* @param node Current node in traversal
* @param remainingSum Remaining sum to achieve targetSum
* @param currentPath Current path from root to current node
* @param allPaths List to collect all paths that sum to targetSum
*/
private void Dfs(TreeNode node, int remainingSum, List<int> currentPath, List<IList<int>> allPaths) {
if (node == null) {
return;
}
// Add current node to the path
currentPath.Add(node.val);
// Check if this is a leaf node and if the current path sums up to targetSum
if (node.left == null && node.right == null && node.val == remainingSum) {
// Add a copy of currentPath to allPaths (C# passes references, so we need to create a copy)
allPaths.Add(new List<int>(currentPath));
} else {
// Recur on the left subtree
Dfs(node.left, remainingSum - node.val, currentPath, allPaths);
// Recur on the right subtree
Dfs(node.right, remainingSum - node.val, currentPath, allPaths);
}
// Backtrack: Remove current node from currentPath to explore other paths
currentPath.RemoveAt(currentPath.Count - 1);
}
}