aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--binary_tree_paths.c46
-rw-r--r--binary_tree_paths.py39
2 files changed, 85 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);
+}
diff --git a/binary_tree_paths.py b/binary_tree_paths.py
new file mode 100644
index 0000000..9b846b0
--- /dev/null
+++ b/binary_tree_paths.py
@@ -0,0 +1,39 @@
+# 257. Binary Tree Paths
+
+"""
+given the 'root' of a binary tree, return all root to leaf paths in any
+order. a leaf is a node with no children
+"""
+
+
+# Definition for a binary tree node.
+class TreeNode(object):
+ def __init__(self, val=0, left=None, right=None):
+ self.val = val
+ self.left = left
+ self.right = right
+
+
+class Solution(object):
+ def binaryTreePaths(self, root):
+ """
+ :type root: TreeNode
+ :rtype: List[str]
+ """
+ if not root:
+ return []
+ ans, stack = [], [(root, "")]
+ while stack:
+ node, ls = stack.pop()
+ if not node.left and not node.right:
+ ans.append(ls + str(node.val))
+ if node.right:
+ stack.append((node.right, ls + str(node.val) + "->"))
+ if node.left:
+ stack.append((node.left, ls + str(node.val) + "->"))
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.binaryTreePaths(root=[1, 2, 3, None, 5]))