List Every Root-to-Leaf Route With a Given Total
Solve this ProblemYou are given the root of a binary tree and an integer target. A route starts at the root, moves downward, and ends at a leaf (a node with no children). Return every route whose node values add up to exactly target, each written as the list of values from the root to the leaf. Routes are listed in left-to-right order of their leaves; if no route works, return an empty list.
You can collect all routes and filter them afterwards, or keep a running "remaining amount" while you walk so that only routes that succeed are ever copied.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100 - ◆
−100 ≤ node.val ≤ 100; −1000 ≤ target ≤ 1000 - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
A route starts at the root and ends at a leaf (a node with no children). Return every route whose values add up to exactly target, each as the list of its node values from the root down. List the routes in left-to-right order of their leaves
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Collect Every Route, Then Filter by Total
BruteFirst gather every root-to-leaf route: walk the tree with one shared path (append on the way down, remove on the way up) and, at each leaf, save a copy of the whole path. Afterwards go through the saved routes, add up each one, and keep those whose total equals the target. It works, but it copies EVERY route (L leaves, each up to h long) even though most of them will be thrown away, and then re-adds every route: O(n · h) time and O(L · h) space for the saved copies.
O(n · h)O(L · h)1class Solution {
2 public List<List<Integer>> routesWithTotal(TreeNode root, int target) {
3 List<List<Integer>> allRoutes = new ArrayList<>();
4 collect(root, new ArrayList<>(), allRoutes);
5 List<List<Integer>> answer = new ArrayList<>();
6 for (List<Integer> route : allRoutes) {
7 int sum = 0;
8 for (int v : route) sum += v;
9 if (sum == target) answer.add(route);
10 }
11 return answer;
12 }
13
14 private void collect(TreeNode node, List<Integer> path, List<List<Integer>> allRoutes) {
15 if (node == null) return;
16 path.add(node.val);
17 if (node.left == null && node.right == null) {
18 allRoutes.add(new ArrayList<>(path));
19 } else {
20 collect(node.left, path, allRoutes);
21 collect(node.right, path, allRoutes);
22 }
23 path.remove(path.size() - 1);
24 }
25}Optimal — Backtrack With a Remaining Amount, Copy Only Hits
OptimalWalk the tree with one shared path and a "remaining" amount that shrinks by each node's value on the way down. At a leaf, the route is a hit exactly when the leaf's value equals the remaining amount; only then is the path copied into the answer. Otherwise recurse into both children (left first, which keeps the required order) and, when leaving the node, remove it from the shared path. Nothing is copied or summed for routes that miss, so the extra space (besides the answer) is just O(h). The worst case is still O(n · h) when many routes hit and have to be copied.
O(n · h)O(h)1class Solution {
2 public List<List<Integer>> routesWithTotal(TreeNode root, int target) {
3 List<List<Integer>> answer = new ArrayList<>();
4 walk(root, target, new ArrayList<>(), answer);
5 return answer;
6 }
7
8 private void walk(TreeNode node, int remaining, List<Integer> path, List<List<Integer>> answer) {
9 if (node == null) return;
10 path.add(node.val);
11 if (node.left == null && node.right == null && node.val == remaining) {
12 answer.add(new ArrayList<>(path));
13 } else {
14 walk(node.left, remaining - node.val, path, answer);
15 walk(node.right, remaining - node.val, path, answer);
16 }
17 path.remove(path.size() - 1);
18 }
19}