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.
1class
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.