aboutsummaryrefslogtreecommitdiff
path: root/binary_tree_paths.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-08-25 00:49:37 -0600
committerJack Sangdahl <[email protected]>2024-08-25 00:49:37 -0600
commitc0d5715e509aead94692d832bb5334759d65e63e (patch)
treee90d9b8d2ed0b27a201808e42a00cd1ba2cd57b2 /binary_tree_paths.c
parentc76c81368f9d66902552aaf8d91fee2a6e67d098 (diff)
downloadleetcode-c0d5715e509aead94692d832bb5334759d65e63e.tar.gz
leetcode-c0d5715e509aead94692d832bb5334759d65e63e.zip
257. binary tree paths
Diffstat (limited to 'binary_tree_paths.c')
-rw-r--r--binary_tree_paths.c46
1 files changed, 46 insertions, 0 deletions
diff --git a/binary_tree_paths.c b/binary_tree_paths.c
new file mode 100644
index 0000000..f2a6448
--- /dev/null
+++ b/binary_tree_paths.c
@@ -0,0 +1,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);
+}