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.
1var binaryTreePaths = function(root) {
2 const paths = [];
3 const dfs = (node, path) => {
4 if (node) {
5 path += node.val;
6 if (!node.left && !node.right) {
7 paths.push(path);
8 } else {
9 path += '->';
10 dfs(node.left, path);
11 dfs(node.right, path);
12 }
13 }
14 };
15 dfs(root, '');
16 return paths;
17};This JavaScript solution leverages a DFS strategy within an inner function, recursively navigating the tree and building paths, which are stored when a leaf node is reached.
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.