## Algorithm

Problem Name: 297. Serialize and Deserialize Binary Tree

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.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

```Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
```

Example 2:

```Input: root = []
Output: []
```

Constraints:

• The number of nodes in the tree is in the range `[0, 104]`.
• `-1000 <= Node.val <= 1000`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int depth(struct TreeNode *n) {
int l, r;
if (!n) return 0;
l = depth(n->left);
r = depth(n->right);
return l > r ? l + 1 : r + 1;
}

#define PUSH(P, N) do { P[sp++] = N; } while (0)
#define POP(P, N)  do { N = P[--sp]; } while (0)

/** Encodes a tree to a single string. */
char* serialize(struct TreeNode* root) {
int sz = 1024 * 10;
int d, n = 0, l = 0;
struct TreeNode **stack;
int sp = 0;
struct TreeNode *node;
char c;

if (!root) return NULL;

d = depth(root);

stack = malloc((d + 1) * sizeof(struct TreeNode *));

PUSH(stack, root);
while (sp) {
if (l + 32 + 8 > sz) {
sz = sz * 2;
}
POP(stack, node);
if (node) {
n ++;
sprintf(str, "%08x", node->val);
str += 8; l += 8;
PUSH(stack, node->right);
PUSH(stack, node->left);
} else {
*str = ','; str += 1; l += 1;
}
}
*str = 0;

// put checksum in the first 8 bytes
sprintf(head, "%08x%08x%08x%08x", 0, d, n, l);
head[HEAD_SZ] = c; //sprintf has put a 0 terminator in the end.

free(stack);

}

int str2num(char *p) {
char buff[9] = { 0 };
strncpy(buff, p, 8);
return strtol(buff, NULL, 16);
}

/** Decodes your encoded data to tree. */
struct TreeNode* deserialize(char* data) {
int n, d, l;
struct TreeNode *buff;
int idx = 0;
struct TreeNode ***stackp;
int sp = 0;
struct TreeNode **pp;
int val;
struct TreeNode *root = NULL, *node;

if (!data) return NULL; // verify checksum

data += 8;

d = str2num(data);

data += 8;

n = str2num(data);

data += 8;

l = str2num(data);

data += 8;

buff = malloc(n * sizeof(struct TreeNode));
stackp = malloc((d + 1) * sizeof(struct TreeNode **));
//assert(buff && stackp);

PUSH(stackp, &root);

while (l > 0) {
POP(stackp, pp);
if (*data == ',') {
*pp = NULL;
data += 1;
l -= 1;
} else {
val = str2num(data);
data += 8;
l -= 8;
node = &buff[idx ++];
node->val = val;
*pp = node;
PUSH(stackp, &node->right);
PUSH(stackp, &node->left);
}
}

free(stackp);

return root;
}
``````
Copy The Code &

Input

cmd
root = [1,2,3,null,null,4,5]

Output

cmd
[1,2,3,null,null,4,5]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Codec {
private:
unordered_maptree2string;
unordered_map < string, TreeNode*>string2tree;
int count = 0;
public:

// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string s = to_string(count++);
tree2string[root] = s;
string2tree[s] = root;
return s;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
return string2tree[data];
}
};
``````
Copy The Code &

Input

cmd
root = [1,2,3,null,null,4,5]

Output

cmd
[1,2,3,null,null,4,5]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
public class Codec {

private static final String NULL_VALUE = "-";
private static final String DELIMETER = " ";

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return NULL_VALUE;
}
StringBuilder sb = new StringBuilder();
Stack < TreeNode> stack = new Stack<>();
while (!stack.isEmpty()) {
TreeNode removed = stack.pop();
if (removed == null) {
sb.append(NULL_VALUE).append(DELIMETER);
continue;
}
sb.append(removed.val).append(DELIMETER);
stack.push(removed.right);
stack.push(removed.left);
}
return sb.toString().trim();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Queue < String> queue = new LinkedList<>(Arrays.asList(data.split("\\s+")));
return helper(queue);
}

private TreeNode helper(Queue < String> queue) {
if (queue.peek().equals(NULL_VALUE)) {
queue.remove();
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(queue.peek()));
queue.remove();
root.left = helper(queue);
root.right = helper(queue);
return root;
}
}
``````
Copy The Code &

Input

cmd
root = []

Output

cmd
[]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const serialize = function(root) {
return rserialize(root, "");
};

function rserialize(root, str) {
if (root === null) {
str += "null,";
} else {
str += root.val + ",";
str = rserialize(root.left, str);
str = rserialize(root.right, str);
}

return str;
}
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
const deserialize = function(data) {
let data_array = data.split(",").filter(el => el !== "");
return rdeserialize(data_array);
};

function rdeserialize(l) {
if (l[0] === "null") {
l.shift();
return null;
}
const root = new TreeNode(+l[0]);
l.shift();
root.left = rdeserialize(l);
root.right = rdeserialize(l);
return root;
}
``````
Copy The Code &

Input

cmd
root = []

Output

cmd
[]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Codec:

def serialize(self, root):
q, s = root and collections.deque([root]), ""
while q:
node = q.popleft()
if node is None:
s += "null#"
else:
s += str(node.val) + "#"
q += [node.left, node.right]
return s

def deserialize(self, data):
data = data and collections.deque(data.split("#"))
q, root = data and collections.deque([TreeNode(int(data.popleft()))]), None
while q:
node = q.popleft()
if not root:
root = node
l, r = data.popleft(), data.popleft()
if l != "null":
node.left = TreeNode(int(l))
q.append(node.left)
if r != "null":
node.right = TreeNode(int(r))
q.append(node.right)
return root
``````
Copy The Code &

Input

cmd
root = [1,2,3,null,null,4,5]

Output

cmd
[1,2,3,null,null,4,5]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;
using System.Text;

namespace LeetCode
{
public class _0297_SerializeandDeserializeBinaryTree
{
private readonly char SPLITTER = ',';
private readonly string NULL_VALUE = "null";

// Encodes a tree to a single string.
public string Serialize(TreeNode root)
{
var sb = new StringBuilder();
Serialize(root, sb);
return sb.ToString();
}

private void Serialize(TreeNode root, StringBuilder sb)
{
if (root == null) sb.Append(NULL_VALUE).Append(SPLITTER);
else
{
sb.Append(root.val.ToString()).Append(SPLITTER);
Serialize(root.left, sb);
Serialize(root.right, sb);
}
}

// Decodes your encoded data to tree.
public TreeNode Deserialize(string data)
{
var splits = data.Split(SPLITTER);
var list = new LinkedList < string>(splits);
return Deserialize(list);
}

private TreeNode Deserialize(LinkedList < string> data)
{
if (data.First.Value == NULL_VALUE)
{
data.Remove(data.First);
return null;
}

var root = new TreeNode(int.Parse(data.First.Value));
data.Remove(data.First);
root.left = Deserialize(data);
root.right = Deserialize(data);
return root;
}
}
}
``````
Copy The Code &

Input

cmd
root = [1,2,3,null,null,4,5]

Output

cmd
[1,2,3,null,null,4,5]