aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-02-21 22:52:44 -0700
committerJack Sangdahl <[email protected]>2025-02-21 22:52:44 -0700
commite2e526d3c6eed3cfded621c2180fb8d3d8817294 (patch)
tree4b6ae5b13f4c18e690fcfc7781444290de080f74
parenteb3697b5c7c80be7c0abf04524408f83cb4ed30d (diff)
downloadleetcode-e2e526d3c6eed3cfded621c2180fb8d3d8817294.tar.gz
leetcode-e2e526d3c6eed3cfded621c2180fb8d3d8817294.zip
1028. recover a tree from preorder traversal
-rw-r--r--recover_tree_preorder.c55
-rw-r--r--recover_tree_preorder.py41
2 files changed, 96 insertions, 0 deletions
diff --git a/recover_tree_preorder.c b/recover_tree_preorder.c
new file mode 100644
index 0000000..d0ee241
--- /dev/null
+++ b/recover_tree_preorder.c
@@ -0,0 +1,55 @@
+// 1028. Recover a Tree From Preorder Traversal
+#include "leetcode.h"
+
+/*
+ * we run a preorder depth-first search (dfs) on the 'root' of a binary tree. at
+ * each node in this traversal, we output 'D' dashes (where 'D' is the depth of
+ * this node), then we output the value of this node. if the depth of a node is
+ * 'D' the depth of its immediate child is 'D + 1'. the depth of the 'root' node
+ * is '0'. if a node has only one child, that child is guaranteed to be the left
+ * child. given the output 'traversal' of this traversal, recover the tree and
+ * return its root.
+ */
+
+struct TreeNode *recoverFromPreorder(char *traversal) {
+ int vals[1000] = {0}, depths[1000] = {0}, n = 0;
+ for (int i = 0; i < strlen(traversal);) {
+ while (traversal[i] == '-') {
+ depths[n]++;
+ i++;
+ }
+ while (traversal[i] >= '0' && traversal[i] <= '9') {
+ vals[n] = vals[n] * 10 + traversal[i] - '0'; // fix
+ i++;
+ }
+ n++;
+ }
+ struct TreeNode *ans = (struct TreeNode *)calloc(n, sizeof(struct TreeNode));
+ for (int i = 0; i < n; i++) {
+ ans[i].val = vals[i];
+ for (int j = i; j >= 0; j--)
+ if (depths[j] < depths[i]) {
+ if (!ans[j].left)
+ ans[j].left = &ans[i];
+ else
+ ans[j].right = &ans[i];
+ break;
+ }
+ }
+ return ans;
+}
+
+int main() {
+ char *t1 = "1-2--3--4-5--6--7";
+ char *t2 = "1-2--3---4-5--6---7";
+ char *t3 = "1-401--349---90--88";
+ struct TreeNode *rfp1 = recoverFromPreorder(t1);
+ struct TreeNode *rfp2 = recoverFromPreorder(t2);
+ struct TreeNode *rfp3 = recoverFromPreorder(t3);
+ treenode_print(rfp1); // expect: [1,2,5,3,4,6,7]
+ treenode_print(rfp2); // expect: [1,2,5,3,null,6,null,4,null,7]
+ treenode_print(rfp3); // expect: [1,401,null,349,88,90]
+ treenode_free(rfp1);
+ treenode_free(rfp2);
+ treenode_free(rfp3);
+}
diff --git a/recover_tree_preorder.py b/recover_tree_preorder.py
new file mode 100644
index 0000000..bc87a66
--- /dev/null
+++ b/recover_tree_preorder.py
@@ -0,0 +1,41 @@
+# 1028. Recover a Tree From Preorder Traversal
+from leetcode import TreeNode
+from re import findall
+
+"""
+we run a preorder depth-first search (dfs) on the 'root' of a binary tree. at
+each node in this traversal, we output 'D' dashes (where 'D' is the depth of
+this node), then we output the value of this node. if the depth of a node is
+'D' the depth of its immediate child is 'D + 1'. the depth of the 'root' node
+is '0'. if a node has only one child, that child is guaranteed to be the left
+child. given the output 'traversal' of this traversal, recover the tree and
+return its root.
+"""
+
+
+class Solution(object):
+ def recoverFromPreorder(self, traversal):
+ """
+ :type traversal: str
+ :rtype: Optional[TreeNode]
+ """
+ nodes = [
+ (len(node[1]), int(node[2])) for node in findall("((-*)(\d+))", traversal)
+ ][::-1]
+
+ def recover(depth):
+ if not nodes or depth != nodes[-1][0]:
+ return None
+ node = TreeNode(nodes.pop()[1])
+ node.left = recover(depth + 1)
+ node.right = recover(depth + 1)
+ return node
+
+ return recover(0)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.recoverFromPreorder(traversal="1-2--3--4-5--6--7"))
+ print(obj.recoverFromPreorder(traversal="1-2--3---4-5--6---7"))
+ print(obj.recoverFromPreorder(traversal="1-401--349---90--88"))