• ㊗️
• 大家
• offer
• 多多！

## Problem

Serialization is 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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Example 1:

Input: root = [2,1,3]
Output: [2,1,3]


Example 2:

Input: root = []
Output: []


Constraints:

• The number of nodes in the tree is in the range [0, 104].
• 0 <= Node.val <= 104
• The input tree is guaranteed to be a binary search tree.

## Code

public class Codec {
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
preorder(root, sb);
return sb.toString();
}

public TreeNode deserialize(String data) {

int i = 0;
while(i + 4 <= data.length()) {
int num = stringToInt(data.substring(i, i + 4));
i += 4;
}

return helper(Integer.MIN_VALUE, Integer.MAX_VALUE, queue);
}

public void preorder(TreeNode root, StringBuilder sb) {
if (root == null) return;

sb.append(intToString(root.val));

preorder(root.left, sb);
preorder(root.right, sb);
}

public TreeNode helper(Integer lower, Integer upper, Queue<Integer> queue) {
if (queue.isEmpty()) return null;

int val = queue.peek();

if (val < lower || val > upper) return null;

queue.poll();

TreeNode root = new TreeNode(val);
root.left = helper(lower, val, queue);
root.right = helper(val, upper, queue);

return root;
}

public String intToString(int x) {
char[] res = new char[4];

for (int i = 0; i < 4; i++) {
res[i] = (char) (x >> (i * 8) & 0xff);
}

return new String(res);
}

public int stringToInt(String s) {
int res = 0;
char[] charArr = s.toCharArray();
for(int i = 0; i < 4; i++){
int num = (int)charArr[i];
res += num << (i * 8);
}
return res;
}
}


297. Serialize and Deserialize Binary Tree

public class Codec {
public String serialize(TreeNode root) {
if(root == null) return "";

StringBuilder res = new StringBuilder();

queue.offer(root);

/*
3
/ \
2   4
/   /
1   5

3 2 4 1 null 5 null null null null null
*/
while(!queue.isEmpty()){
TreeNode node = queue.poll();

if(node == null){
res.append("null ");
continue;
}

res.append(node.val + " ");
queue.offer(node.left);
queue.offer(node.right);
}

return res.toString();
}

public TreeNode deserialize(String data) {
if(data == null || data.length() == 0) return null;

String[] strs = data.split(" ");
TreeNode root = new TreeNode(Integer.valueOf(strs[0]));

queue.offer(root);

for(int i = 1; i < strs.length; i++){
TreeNode node = queue.poll();

if(!strs[i].equals("null")){
node.left = new TreeNode(Integer.valueOf(strs[i]));
queue.offer(node.left);
}

i++;

if(!strs[i].equals("null")){
node.right = new TreeNode(Integer.valueOf(strs[i]));
queue.offer(node.right);
}
}

return root;
}
}