# 297. Serialize and Deserialize Binary Tree (Hard)

https://leetcode.com/problems/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.

Example:

```You may serialize the following tree:

1
/ \
2   3
/ \
4   5

as `"[1,2,3,null,null,4,5]"`
```

Clarification: The above 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.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

## Solutions

``````class Codec {

// The most crucial stuff is how we define the visiting path, here we will take a
// simple string as an example to demonstrate. For node N, the path expression is
// "lllr", which denotes the sequence of nodes we take and it can be interpreted as
// step 1. move left; step 2. move left; step 3. move left; step 4. move right.

// Solution A

// 1. Sort the max depth of tree n.
// 2. Define an array (2^n)-1 initialized with null
// 3. Recurse the tree nodes and work out the corresponding index of each node
// in above array in light of the path, then set the node value

// Solution B

// 1. Define a List which is used to keep the unique path toward specific node.
// 2. Recurse the tree nodes and combine the visiting path and node value, then store
// it to above List. The combination looks like "llr=n", where l and r are
// direction of branch; represents the link between two nodes; = signifies the separator
// between path and node value.

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "";
}

List<String> nodePaths = new ArrayList<>();

recurse(root, "", nodePaths);

String ans = "";
for (String path : nodePaths) {
ans += path + " ";
}

return ans.trim();
}

private void recurse(TreeNode node, String path, List<String> nodePaths) {
if (node == null) {
return;
}

// remove prefix '>'

recurse(node.left, path + "l", nodePaths);

recurse(node.right, path + "r", nodePaths);
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
TreeNode root = null;

String[] nodeStrs = data.split(" ");
for (String str : nodeStrs) {
String path = str.split("#");
int val = Integer.valueOf(str.split("#"));

if (path == null || path.length() == 0) {
root = new TreeNode(val);

continue;
}

TreeNode tmp = root;
for (int i = 0; i < path.length(); i++) {
int c = path.charAt(i);

if (i == path.length() - 1) {
if (c == 'l') {
tmp.left = new TreeNode(val);
} else {
tmp.right = new TreeNode(val);
}

break;
}

if (path.charAt(i) == 'l') {
tmp = tmp.left;
} else {
tmp = tmp.right;
}
}
}

return root;
}
}
``````