Leetcode Serialize and Deserialize Binary Tree problem solution

In this Leetcode Serialize and Deserialize Binary Tree problem solution Serialization 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 across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Problem solution in Python.

```from collections import deque

class Codec:

def serialize(self, root):
"""Encodes a tree to a single string.

:type root: TreeNode
:rtype: str
"""
get_val = lambda item: item.val if item else None
q = deque()

if not root:
return str([])
else:
res = [root.val]
q.append(root)
while q:
l=[]
len_q = len(q)
for i in range(len_q):
item = q.popleft()
if item and item.left:
q.append(item.left)
if item and item.right:
q.append(item.right)
l.append(get_val(item.left))
l.append(get_val(item.right))
if not all(x is None for x in l):
res += l
ind =len(res)
for i in res[::-1]:
if i is not None:break
else:ind-=1
return str(res[:ind])

def deserialize(self, data):
if len(data)==0 or data=='[]':
return []
de_data = data[1:-1].split(', ')
return [int(d) if d!='None' else None for d in de_data]
```

Problem solution in Java.

```public class Codec {
List<String> count;
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
count = new ArrayList<>();
iter(root, 1);
count.remove(0);
String ret = "";
for (String i: count){
ret = ret+i;
ret = ret+",";
}
ret.substring(0, ret.length()-1);
return ret;
}

public void iter(TreeNode root, int index){
if (root == null) return;
while (index >= count.size())
iter(root.left, index*2);
iter(root.right, index*2+1);
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] raw = data.split(",");
return iter2(raw, 1);
}

public TreeNode iter2(String[] raw, int index){
if (raw[index-1] == "n")
return null;
TreeNode cur = new TreeNode(Integer.valueOf(raw[index-1]));
cur.left = iter2(raw, index*2);
cur.right = iter2(raw, index*2+1);
return cur;
}
}
```

Problem solution in C++.

```class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (root == NULL)   return " ";
list<TreeNode*> ver;
ver.push_back(root);
string str;
while(!ver.empty()) {
TreeNode* tr = ver.front();
ver.pop_front();
if (tr == NULL) {
str.append(":,");
continue;
} else {
string s = to_string(tr->val) + ",";
str.append(s);
}
ver.push_back(tr->left);
ver.push_back(tr->right);
}
return str;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data == " ")    return NULL;
int id = data.find(',');
string s;

s = data.substr(0, id);
id += 1;
int val = stoi(s);
TreeNode* root = new TreeNode(val);
list<TreeNode*> ver;
ver.push_back(root);
while(!ver.empty()) {
TreeNode* tr = ver.front();
ver.pop_front();
vector<string> v;
for (int i = 0; i < 2; i++) {
int idx = data.find(',', id);
s = data.substr(id, idx - id);
id = idx + 1;
v.push_back(s);
s.clear();
}
if (v[0] != ":")    tr->left = new TreeNode(stoi(v[0]));
if (v[1] != ":")    tr->right = new TreeNode(stoi(v[1]));
if (tr->left)   ver.push_back(tr->left);
if (tr->right)  ver.push_back(tr->right);
}
return root;
}
};
```

Problem solution in C.

```#define WIDE_RANGE

#ifdef WIDE_RANGE
typedef uint32_t keyy_t;
#else
typedef uint16_t keyy_t;
#endif // WIDE_RANGE

struct srlz_data {
int val;
keyy_t loff, roff;
} __attribute__ ((packed));

struct srlz {
size_t sz; // To help on-disk storage/retrieval, etc
size_t n;
struct srlz_data z[100000];
} __attribute__ ((packed));

char* serialize(struct TreeNode* root) {
int of[KEY_MASK] = { 0 }, i = 1, k;
struct TreeNode *n[10000] = { root };
struct srlz *d = malloc(sizeof *d);
struct srlz_data *z = d->z;
d->sz = sizeof *d;
of[KEY(root)] = i++;
for (int f = 0, b = 1 ; root && f < b ; f++) {
z[of[k = KEY(n[f])]].val = n[f]->val;
z[of[k]].loff = n[f]->left ? of[KEY(n[b++] = n[f]->left)] = i++ : 0;
z[of[k]].roff = n[f]->right ? of[KEY(n[b++] = n[f]->right)] = i++ : 0;
}
return d->n = root ? i : 0, (char *)d;
}

struct TreeNode* deserialize(char* data) {
struct srlz *d = (void *)data;
struct srlz_data *z = d->z + 1;
size_t c = d->n;
struct TreeNode *n[100000] = { [1] = c ? malloc(sizeof **n) : NULL };
for (int i = 1 ; i < c ; n[i++]->val = z++->val) {
n[i]->left = z->loff ? n[z->loff] = malloc(sizeof **n) : NULL;
n[i]->right = z->roff ? n[z->roff] = malloc(sizeof **n) : NULL;
}
return n[1];
}
```