1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
// 257. Binary Tree Paths
#include "leetcode.h"
/*
* given the 'root' of a binary tree, return all root to leaf paths in any
* order. a leaf is a node with no children
*/
void dfs(struct TreeNode *node, char **paths, char *path, int path_size,
int *path_num) {
if (!node)
return;
int size = snprintf(path + path_size, 7, "%d->", node->val);
path_size += size;
if (!node->left && !node->right) {
paths[*path_num] = (char *)malloc((path_size - 1) * sizeof(char));
memcpy(paths[*path_num], path, path_size - 2);
paths[*path_num][path_size - 2] = '\0';
(*path_num)++;
}
dfs(node->left, paths, path, path_size, path_num);
dfs(node->right, paths, path, path_size, path_num);
}
char **binaryTreePaths(struct TreeNode *root, int *returnSize) {
// 1 + 2 + 4 + 8 + 16 + 32 + "37" = 100 implies max path possibility is 37
char **paths = (char **)malloc(37 * sizeof(char *));
// 100 * 4("-100") + 99 * 2("->") + 1("\0")
char *path = (char *)malloc(599 * sizeof(char));
*returnSize = 0;
dfs(root, paths, path, 0, returnSize);
free(path);
return paths;
}
int main() {
int returnSize;
struct TreeNode *root = treenode_create(1);
root->left = treenode_create(2);
root->left->right = treenode_create(5);
root->right = treenode_create(3);
char **btp = binaryTreePaths(root, &returnSize);
for (int i = 0; i < returnSize; i++)
printf("%s ", btp[i]); // expect: "1->2->5","1->3"
free(btp);
}
|