Sponsored
Sponsored
This approach uses Depth-First Search (DFS) to explore all paths from the root to the leaf nodes. Starting from the root, we recursively visit each node, accumulating the current path. When a leaf node is reached, we add the accumulated path to a list of paths. This can be implemented recursively and is optimal given the constraints.
Time Complexity: O(n), where n is the number of nodes in the tree, as we visit each node once.
Space Complexity: O(n), for the space used to store the recursion stack and the result paths.
1import java.util.ArrayList;
2import java.util.List;
3
4class TreeNode {
5 int val;
6 TreeNode left;
7 TreeNode right;
8 TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12 public List<String> binaryTreePaths(TreeNode root) {
13 List<String> paths = new ArrayList<>();
14 if (root != null) dfs(root, "", paths);
15 return paths;
16 }
17
18 private void dfs(TreeNode node, String path, List<String> paths) {
19 if (node != null) {
20 path += Integer.toString(node.val);
21 if (node.left == null && node.right == null) { // Leaf
22 paths.add(path);
23 } else {
24 path += "->";
25 dfs(node.left, path, paths);
26 dfs(node.right, path, paths);
27 }
28 }
29 }
30}This Java solution uses DFS recursively to traverse each node and build paths as strings. When reaching leaf nodes, it stores the accumulated path to the list of paths.
This approach utilizes an iterative Depth-First Search (DFS) with a stack. By storing the nodes and their paths on the stack, we can simulate the recursive DFS stack. This allows for constructing the paths through iterative backtracking.
Time Complexity: O(n), traversing each node once.
Space Complexity: O(n), as we maintain a stack proportional to the tree height.
1#
This iterative C solution uses a stack to hold nodes and their accumulated paths. When processing each node, its path is updated and child nodes are added to the stack along with updated paths. Leaf nodes are treated as path endpoints.