// 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); }