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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
6 public TreeNode left;
7 public TreeNode right;
8 public TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12 public IList<string> BinaryTreePaths(TreeNode root) {
13 List<string> paths = new List<string>();
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 += node.val;
21 if (node.left == null && node.right == null) { // Leaf node
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 C# approach utilizes a recursive method for generating paths similar to other languages. Each path is built from the root to the leaves, utilizing a recursive call stack to track the depth and path.
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
The Java solution employs a stack to maintain nodes alongside accumulated path strings. As each node is processed, its path is managed, adding to the path list on completion of a root-to-leaf traversal.
An additional Pair class is used to handle the node and path pairing for stack operations.