diff options
author | Jack Sangdahl <[email protected]> | 2024-11-25 22:26:38 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-11-25 22:26:38 -0700 |
commit | c3ac4d44c7b5e7c58688e49985ea2aeff3e5c6c7 (patch) | |
tree | bfecf94e8f15d0fc7ac7e4b1307d291de403765a | |
parent | eaddd863d10736dddb4ad399f37c1bc6022d4179 (diff) | |
download | leetcode-c3ac4d44c7b5e7c58688e49985ea2aeff3e5c6c7.tar.gz leetcode-c3ac4d44c7b5e7c58688e49985ea2aeff3e5c6c7.zip |
297. serialise and deserialise binary tree
-rw-r--r-- | serialise_deserialise_bt.c | 171 | ||||
-rw-r--r-- | serialise_deserialise_bt.py | 70 |
2 files changed, 241 insertions, 0 deletions
diff --git a/serialise_deserialise_bt.c b/serialise_deserialise_bt.c new file mode 100644 index 0000000..77e58fc --- /dev/null +++ b/serialise_deserialise_bt.c @@ -0,0 +1,171 @@ +// 297. Serialize and Deserialize Binary Tree +#include "leetcode.h" + +/* + * serialisation is the process of converting a data structure or object into a + * sequence of bits so that it can be stored in a file or memory buffer, or + * transmitted acorss a network connection link to be reconstructed later in the + * same or another computer environment. design an algorithm to serialise and + * deserialise a binary tree. there is no restriction on how your serialisation + * and deserialisation algorithm shouldd work. you just need to ensure that a + * binary tree can be serialised to a string and this string can be deserialised + * to the original tree structure. + */ + +struct list { + char **data; + int pos; + int size; +}; + +int comma_cnt(char *s) { + int cnt = 0; + while (*s != '\0') { + cnt += *s == ','; + ++s; + }; + return cnt; +} + +struct list *split(char *s, int size) { + struct list *l = (struct list *)malloc(sizeof(struct list)); + char **res = (char **)malloc(size * sizeof(char *)), *q = s; + for (int i = 0; i < size; ++i) { + while (*q != ',' && *q != '\0') + ++q; + if (*q == ',') { + *q = '\0'; + ++q; + } + res[i] = s; + s = q; + } + l->data = res; + l->pos = 0; + l->size = size; + return l; +} + +char *pop(struct list *l) { + if (l->pos >= l->size) + return NULL; + return l->data[l->pos++]; +} + +char *cleanup(char *s) { + int i = 0, j = 0; + if (s[j] == '[') + ++j; + while (s[j] != ']' && s[j] != '\0') { + if (!isspace(s[j])) + s[i++] = s[j]; + ++j; + } + s[i] = '\0'; + return s; +} + +/** Encodes a tree to a single string. */ +char *serialize(struct TreeNode *root) { + if (!root) + return NULL; + struct TreeNode *queue[21001]; + int head = 0, tail = 0; + bool has_nodes; + struct TreeNode *n; + char *s = (char *)malloc(10 * sizeof(char)), num_str[10]; + int sl = 1, max_sl = 10; + s[0] = '['; + queue[tail++] = root; + while (head != tail) { + n = queue[head++]; + if (n) { + sprintf(num_str, "%d", n->val); + if (sl + strlen(num_str) + 4 >= max_sl) { + max_sl *= 2; + s = (char *)realloc(s, max_sl); + } + strcpy(s + sl, num_str); + sl += strlen(num_str); + s[sl++] = ','; + queue[tail++] = n->left; + queue[tail++] = n->right; + } else { + if (sl + 7 > max_sl) { + max_sl *= 2; + s = (char *)realloc(s, max_sl); + } + strcpy(s + sl, "null,"); + sl += 5; + } + has_nodes = false; + for (int i = head; i < tail; i++) + if (queue[i]) { + has_nodes = true; + break; + } + if (!has_nodes) + head = tail; + } + s[sl - 1] = ']'; + s[sl] = '\0'; + return s; +} + +/** Decodes your encoded data to tree. */ +struct TreeNode *deserialize(char *data) { + if (!data) + return NULL; + data = cleanup(data); + int num_nodes = comma_cnt(data) + 1, head = 0, tail = 0; + struct list *l = split(data, num_nodes); + struct TreeNode *queue[num_nodes], *root, *n, *m; + char *entry = pop(l); + if (!entry) + return NULL; + root = (struct TreeNode *)malloc(sizeof(struct TreeNode)); + root->val = atoi(entry); + root->left = NULL; + root->right = NULL; + queue[tail++] = root; + while (head != tail) { + n = queue[head++]; + entry = pop(l); + if (entry && strcmp(entry, "null")) { + m = (struct TreeNode *)malloc(sizeof(struct TreeNode)); + m->val = atoi(entry); + m->left = NULL; + m->right = NULL; + n->left = m; + queue[tail++] = m; + } + entry = pop(l); + if (entry && strcmp(entry, "null")) { + m = (struct TreeNode *)malloc(sizeof(struct TreeNode)); + m->val = atoi(entry); + m->left = NULL; + m->right = NULL; + n->right = m; + queue[tail++] = m; + } + } + return root; +} + +// Your functions will be called as such: +// char* data = serialize(root); +// deserialize(data); + +int main() { + struct TreeNode *root = treenode_create(1); + root->left = treenode_create(2); + root->right = treenode_create(3); + root->right->left = treenode_create(4); + root->right->right = treenode_create(5); + char *data = serialize(root); + struct TreeNode *ds = deserialize(data); + treenode_print(ds); // expect: 1 2 3 nll null 4 5 + treenode_free(root); + treenode_free(ds); + free(data); +} diff --git a/serialise_deserialise_bt.py b/serialise_deserialise_bt.py new file mode 100644 index 0000000..4722179 --- /dev/null +++ b/serialise_deserialise_bt.py @@ -0,0 +1,70 @@ +# 297. Serialize and Deserialize Binary Tree + +""" +serialisation is the process of converting a data structure or object into a +sequence of bits so that it can be stored in a file or memory buffer, or +transmitted acorss a network connection link to be reconstructed later in the +same or another computer environment. design an algorithm to serialise and +deserialise a binary tree. there is no restriction on how your serialisation +and deserialisation algorithm shouldd work. you just need to ensure that a +binary tree can be serialised to a string and this string can be deserialised +to the original tree structure. +""" + + +# Definition for a binary tree node. +class TreeNode(object): + def __init__(self, x): + self.val = x + self.left = None + self.right = None + + +class Codec: + def serialize(self, root): + """Encodes a tree to a single string. + + :type root: TreeNode + :rtype: str + """ + vals = [] + + def ser(node): + if node: + vals.append(str(node.val)) + ser(node.left) + ser(node.right) + + ser(root) + return "".join(vals) + + def deserialize(self, data): + """Decodes your encoded data to tree. + + :type data: str + :rtype: TreeNode + """ + vals = iter(data.split()) + + def deser(): + val = next(vals) + if val == "#": + return None + node = TreeNode(int(val)) + node.left = deser() + node.right = deser() + return node + + return deser() + + +# Your Codec object will be instantiated and called as such: +# ser = Codec() +# deser = Codec() +# ans = deser.deserialize(ser.serialize(root)) + +if __name__ == "__main__": + ser = Codec() + deser = Codec() + root = [1, 2, 3, None, None, 4, 5] + print(deser.deserialize(ser.serialize(root))) |