113. Path Sum II
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.
Approach 1: DFS Recursive
class Solution {
public List> pathSum(TreeNode root, int targetSum) {
List> answer = new ArrayList<>();
List list = new ArrayList<>();
if (root == null)
return answer;
dfs(answer, list, root, targetSum, 0);
return answer;
}
private void dfs(List> answer, List sofar, TreeNode node, int targetSum, int currentSum) {
if (node.left == null && node.right == null) {
int lastValue = currentSum + node.val;
if (lastValue == targetSum) {
sofar.add(node.val);
answer.add(new ArrayList(sofar));
sofar.remove(sofar.size() - 1);
}
return;
}
int nextSum = currentSum + node.val;
sofar.add(node.val);
if (node.left != null)
dfs(answer, sofar, node.left, targetSum, nextSum);
if (node.right != null)
dfs(answer, sofar, node.right, targetSum, nextSum);
sofar.remove(sofar.size() - 1);
}
}
Time Complexity: O(n) and Space Complexity: O(n)
Approach 2: Recursive solution with backtracking
class Solution {
public List> pathSum(TreeNode root, int targetSum) {
List> answer = new ArrayList<>();
// If empty tree return empty list.
if (root == null)
return answer;
findPaths(root, targetSum, answer, new ArrayList<>());
return answer;
}
public void findPaths(TreeNode root, int target, List> answer, List current) {
// For leaf node, check if the value is equal to the remaining target, If true
// add the value to current list and then current to the answer.
if (root.left == null && root.right == null) {
if (target == root.val) {
current.add(root.val);
answer.add(List.copyOf(current));
// Remove the last element from the current because it will back track and it
// should not have that value in the list.
current.remove(current.size() - 1);
}
return;
}
// Add the root value to the current list so that if a path is found, the path
// can be added to the answer.
current.add(root.val);
// check for left and right subtree after subtracting the value from the target
// sum.
if (root.left != null)
findPaths(root.left, target - root.val, answer, current);
if (root.right != null)
findPaths(root.right, target - root.val, answer, current);
// Remove the last element from the current because it will back track and it
// should not have that value in the list.
current.remove(current.size() - 1);
}
}
Time Complexity: O(n) and Space Complexity: O(n)
Introduction
The "Path Sum II" problem is a tree-based problem where you are given a binary tree and an integer target sum. The task is to find all root-to-leaf paths where the sum of the node values along the path equals the target sum. A root-to-leaf path is a path that starts from the root and ends at a leaf node.
Problem Statement
Given the root of a binary tree and a target sum, return all root-to-leaf paths where the sum of the node values equals the target sum. Each path should be returned as a list of the node values. The path must go from the root node to a leaf node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
The tree node structure is given above. The goal is to return all the root-to-leaf paths where the sum of the node values is equal to the target sum.
Approach
To solve this problem, we can use depth-first search (DFS) to traverse the tree while keeping track of the current path and sum. As we traverse, we add the current node’s value to the path and subtract the node's value from the remaining sum.
- Start by performing a DFS traversal from the root node.
- At each node, subtract the node's value from the remaining target sum and add the node's value to the current path.
- If the current node is a leaf and the remaining sum is zero, add the current path to the result.
- Recursively continue the traversal for the left and right subtrees.
- Backtrack by removing the last node from the current path once the DFS finishes exploring a node's left or right subtree.
Algorithm
The algorithm follows these steps:
- Define a helper function that performs a DFS traversal while maintaining the current path and target sum.
- At each node, subtract the node’s value from the target sum and add the node’s value to the current path.
- If the node is a leaf and the target sum is zero, add the current path to the result.
- Recursively traverse the left and right subtrees.
- Backtrack by removing the node from the current path once its left and right subtrees have been explored.
- Return the result after the DFS traversal is complete.
This approach ensures that all root-to-leaf paths are explored, and the valid paths (where the sum of node values equals the target sum) are collected.
Example
Consider the following binary tree and target sum of 22:
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
In this example, the following paths have a sum of 22: - Path 1: 5 → 4 → 11 → 2 (sum = 22) - Path 2: 5 → 8 → 4 → 1 (sum = 22)
Therefore, the solution should return the following list of paths: - [[5, 4, 11, 2], [5, 8, 4, 1]]
Code Implementation
Below is the Python implementation of the algorithm to find all root-to-leaf paths where the sum equals the target sum:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def pathSum(root, target):
result = []
def dfs(node, current_path, remaining_sum):
if not node:
return
# Add the current node to the path
current_path.append(node.val)
remaining_sum -= node.val
# If it's a leaf node and the remaining sum is zero, add the path to the result
if not node.left and not node.right and remaining_sum == 0:
result.append(list(current_path))
# Recursively explore the left and right subtrees
dfs(node.left, current_path, remaining_sum)
dfs(node.right, current_path, remaining_sum)
# Backtrack by removing the last node from the current path
current_path.pop()
# Call the DFS function starting from the root with an empty path and the target sum
dfs(root, [], target)
return result
In this code: - The `dfs` function is a recursive helper that performs a depth-first search to explore all root-to-leaf paths. - The `current_path` keeps track of the current path from the root to the current node, and `remaining_sum` is the target sum minus the sum of the node values along the current path. - If a leaf node is reached and the remaining sum is zero, the current path is added to the result list. - The algorithm backtracks by removing the last node from the path after exploring both left and right subtrees of each node.
Time Complexity
The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. In the worst case, we must visit each node once during the DFS traversal.
The space complexity is O(h), where h is the height of the tree. This space is used by the recursion stack during the DFS traversal. In the worst case, the height of the tree is O(n) (for a skewed tree), and in the best case, it is O(log n) (for a balanced tree).
Conclusion
The "Path Sum II" problem is an excellent example of using depth-first search (DFS) with backtracking to explore all root-to-leaf paths and find the paths that sum up to a target value. By maintaining the current path and subtracting the node values from the target sum, we can efficiently find all valid paths.
