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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def binaryTreePaths(self, root: TreeNode) -> List[str]:
9 def dfs(node, path):
10 if node:
11 path += str(node.val)
12 if not node.left and not node.right: # Leaf node
13 paths.append(path)
14 else:
15 path += '->'
16 dfs(node.left, path)
17 dfs(node.right, path)
18
19 paths = []
20 dfs(root, '')
21 return pathsThis Python solution leverages the recursive DFS approach to gather paths. Leaf nodes signal the end of a path, which is then appended to the results.
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
Using a stack with tuples comprising nodes and path strings, this Python solution iteratively processes the tree. Leaf nodes add completed paths to the paths list, leveraging stack operations for state management.