Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of node values along the path equals targetSum.
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: Two root-to-leaf paths sum to 22.
The number of nodes is in the range [0, 5000]-1000 <= Node.val <= 1000This is DFS with backtracking: build up a path as you descend, and undo that addition when you backtrack up.
A leaf is a node with no left AND no right child — that's your termination check for 'is this a complete path.'
You need a NEW copy of the current path list when you find a valid one — reusing the same mutable list reference means every collected answer would end up referencing the same (later-mutated) list.
public List<List<Integer>> pathSumBruteForce(TreeNode root, int targetSum) {
List<List<Integer>> allPaths = new ArrayList<>();
collectAllPaths(root, new ArrayList<>(), allPaths);
List<List<Integer>> result = new ArrayList<>();
for (List<Integer> path : allPaths) {
long sum = 0;
for (int v : path) sum += v;
if (sum == targetSum) result.add(path);
}
return result;
}
private void collectAllPaths(TreeNode node, List<Integer> path, List<List<Integer>> allPaths) {
if (node == null) return;
path.add(node.val);
if (node.left == null && node.right == null) allPaths.add(new ArrayList<>(path));
else { collectAllPaths(node.left, path, allPaths); collectAllPaths(node.right, path, allPaths); }
path.remove(path.size() - 1);
}Time: O(n^2) worst case · Space: O(n) for all collected paths