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 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: []
Constraints:
[0, 5000]
.-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
Given the root of a binary tree and an integer targetSum
, find all root-to-leaf paths where the sum of node values equals targetSum
. Return each path as a list of node values.
This problem is best solved using Depth-First Search (DFS). DFS explores a tree by going as deep as possible along each branch before backtracking. We'll use a recursive approach to explore all paths.
Algorithm:
null
, return.targetSum
.targetSum
is 0, add the current path to the result.# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
result = []
path = []
def dfs(node, current_sum):
if not node:
return
current_sum -= node.val
path.append(node.val)
if not node.left and not node.right and current_sum == 0:
result.append(path.copy())
dfs(node.left, current_sum)
dfs(node.right, current_sum)
path.pop() # Backtrack
dfs(root, targetSum)
return result
import java.util.*;
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
dfs(root, targetSum);
return result;
}
private void dfs(TreeNode node, int currentSum) {
if (node == null) {
return;
}
currentSum -= node.val;
path.add(node.val);
if (node.left == null && node.right == null && currentSum == 0) {
result.add(new ArrayList<>(path));
}
dfs(node.left, currentSum);
dfs(node.right, currentSum);
path.remove(path.size() - 1); // Backtrack
}
}
(Other languages like C++, Go, JavaScript, and Rust would follow a very similar structure, adapting the syntax and data structures to the specific language.)
This DFS solution efficiently finds all root-to-leaf paths with the target sum, offering a clear and concise approach to solving the problem. The backtracking step is crucial for correctly exploring all possible paths.