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 <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5// Definition for a binary tree node.
6struct TreeNode {
7 int val;
8 struct TreeNode *left;
9 struct TreeNode *right;
10};
11
12void dfs(struct TreeNode* node, char* path, char** paths, int* size) {
13 if (!node) return;
14 char buffer[16];
15 sprintf(buffer, "%d", node->val);
16 if (strlen(path) != 0) {
17 strcat(path, "->");
18 }
19 strcat(path, buffer);
20 if (!node->left && !node->right) {
21 paths[*size] = strdup(path);
22 (*size)++;
23 } else {
24 char temp[512];
25 strcpy(temp, path);
26 dfs(node->left, path, paths, size);
27 strcpy(path, temp);
28 dfs(node->right, path, paths, size);
29 }
30}
31
32char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
33 char** paths = (char**)malloc(100 * sizeof(char*));
34 char path[512] = "";
35 *returnSize = 0;
36 dfs(root, path, paths, returnSize);
37 return paths;
38}This C solution uses a recursive DFS function to build the path as a string and store it in an array when a leaf node is reached. - Root value is added to the path for each node and if a leaf is reached, the path is stored in a results array.
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#include <vector>
2#include <string>
#include <stack>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
std::vector<std::string> binaryTreePaths(TreeNode* root) {
std::vector<std::string> paths;
if (!root) return paths;
std::stack<std::pair<TreeNode*, std::string>> stack;
stack.push({root, std::to_string(root->val)});
while (!stack.empty()) {
auto [node, path] = stack.top(); stack.pop();
if (!node->left && !node->right) {
paths.push_back(path);
}
if (node->right) {
stack.push({node->right, path + "->" + std::to_string(node->right->val)});
}
if (node->left) {
stack.push({node->left, path + "->" + std::to_string(node->left->val)});
}
}
return paths;
}In this C++ solution, a stack simulates the recursive call stack by holding nodes and path strings. On processing nodes, if they are leaves, the path is added to the result. Otherwise, child nodes are stacked with updated paths.