Write Out Every Route From the Root to a Leaf
Solve this ProblemYou are given the root of a binary tree. Return every route that starts at the root and ends at a leaf (a node with no children), each written as the node values joined by "->". Routes that go through a node's left child must be listed before routes that go through its right child.
You can pass a growing string down the recursion, or you can keep one shared path that grows on the way down and shrinks (backtracks) on the way back up.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100 - ◆
−100 ≤ node.val ≤ 100 - ◆
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 - ◆
Return every root-to-leaf route as a string of the node values joined by "->" (for example "8->3->1"). List the routes in left-to-right order of their leaves — routes through the left subtree before routes through the right subtree. An empty tree has no routes
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Build a New String at Every Step
GoodRecurse down the tree carrying the route so far as a string. Stepping to a child creates a NEW string: the old route plus "->" plus the child's value. When a node has no children the string is complete, so it is added to the answer. Trying the left child before the right child gives the required left-to-right order. It is correct, but every step builds a fresh string by copying the previous one, so a route of length h costs O(h) per step and the work is O(n · h) overall.
O(n · h)O(n · h)1class Solution {
2 public List<String> rootToLeafRoutes(TreeNode root) {
3 List<String> routes = new ArrayList<>();
4 if (root == null) return routes;
5 collect(root, String.valueOf(root.val), routes);
6 return routes;
7 }
8
9 private void collect(TreeNode node, String path, List<String> routes) {
10 if (node.left == null && node.right == null) {
11 routes.add(path);
12 return;
13 }
14 if (node.left != null) collect(node.left, path + "->" + node.left.val, routes);
15 if (node.right != null) collect(node.right, path + "->" + node.right.val, routes);
16 }
17}Optimal — Backtracking With One Shared Path
OptimalKeep a single path (a list of values) that is shared by the whole walk. On entering a node, append its value. If the node is a leaf, join the path once into a string and record it; otherwise walk the left child and then the right child. On leaving the node, remove its value again ("backtrack") so the path is exactly the route to the parent for the next sibling. Strings are built only at leaves (L of them), instead of at every step; besides the answer itself, the extra space is just the path and recursion, O(h).
O(n + L · h)O(h)1class Solution {
2 public List<String> rootToLeafRoutes(TreeNode root) {
3 List<String> routes = new ArrayList<>();
4 walk(root, new ArrayList<>(), routes);
5 return routes;
6 }
7
8 private void walk(TreeNode node, List<Integer> path, List<String> routes) {
9 if (node == null) return;
10 path.add(node.val);
11 if (node.left == null && node.right == null) {
12 StringBuilder sb = new StringBuilder();
13 for (int i = 0; i < path.size(); i++) {
14 if (i > 0) sb.append("->");
15 sb.append(path.get(i));
16 }
17 routes.add(sb.toString());
18 } else {
19 walk(node.left, path, routes);
20 walk(node.right, path, routes);
21 }
22 path.remove(path.size() - 1);
23 }
24}