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.
1#include <vector>
2#include <string>
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11void dfs(TreeNode* node, std::string path, std::vector<std::string>& paths) {
12 if (!node) return;
13 path += std::to_string(node->val);
14 if (!node->left && !node->right) {
15 paths.push_back(path);
16 } else {
17 path += "->";
18 dfs(node->left, path, paths);
19 dfs(node->right, path, paths);
20 }
21}
22
23std::vector<std::string> binaryTreePaths(TreeNode* root) {
24 std::vector<std::string> paths;
25 dfs(root, "", paths);
26 return paths;
27}This C++ solution recursively constructs paths by accumulating node values in a string. The current path is added to the list when a leaf is reached. Backtracking is naturally handled by recursion since we use the same path string at each recursive depth.
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.