diff options
author | Jack Sangdahl <[email protected]> | 2025-02-21 22:52:44 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-02-21 22:52:44 -0700 |
commit | e2e526d3c6eed3cfded621c2180fb8d3d8817294 (patch) | |
tree | 4b6ae5b13f4c18e690fcfc7781444290de080f74 | |
parent | eb3697b5c7c80be7c0abf04524408f83cb4ed30d (diff) | |
download | leetcode-e2e526d3c6eed3cfded621c2180fb8d3d8817294.tar.gz leetcode-e2e526d3c6eed3cfded621c2180fb8d3d8817294.zip |
1028. recover a tree from preorder traversal
-rw-r--r-- | recover_tree_preorder.c | 55 | ||||
-rw-r--r-- | recover_tree_preorder.py | 41 |
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")) |