1. 二叉搜索树的序列化和反序列化
设计一个算法来序列化和反序列化二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。编码的字符串应尽可能紧凑。
我们说过一切对树的操作，均建立在树的遍历之上的。
假设我们需要保存的数结构：
1.1 算法分析
那我们需要采用一种遍历的方式来进行操作：
（1）中序遍历
我们对BST进行中序遍历，可以得到10 20 30 35 40 50，但是我们无法从中推断出原始的二叉树结构。
（2）后序遍历
若是选用后序遍历呢？我们要知道后序遍历是先左右节点再根节点，那么重新构造二叉树时也会有麻烦，因为构造的时候需要先构造父节点。而显然，后序遍历先读取孩子节点而后才是父节点。
（3）前序遍历
我们选用前序遍历，便可以先获取到根节点，然后，根据二叉搜索树的左子树<根节点<右子树的关系，便可重构一棵搜索二叉树。
1.2 算法实现
如何将一个字符串重建而一棵二叉树？
五分钟玩转面试考点-数据结构-重建二叉树（节节平等，伪-后序）
首先将一个字符串切割为数组，然后找到一个规律：
上图的原搜索二叉树的前序遍历为：
30 20 10 40 35 50
我们看到，30是根节点，第一个大于根节点的元素就是右子树的元素。
于是，我们就可以构造出一个二叉树了。
小胖也是这么做的，但是在实现的过程中，有一点没有考虑到，就是若整个字符串都比根节点小（即：均是左子树）。
算法实现：
前序遍历，将二叉树转化为字符串：
//根据前序遍历拆分二叉树
public String serialize(TreeNode root) {
if (root == null) {
return null;
}
StringBuilder sb = new StringBuilder();
serialize(root, sb);
String s1 = sb.toString();
if (s1.endsWith(",")) {
s1 = s1.substring(0, s1.length() - 1);
}
return s1;
}
//前序遍历二叉树，将其保存到字符串中
public void serialize(TreeNode root, StringBuilder str) {
if (root == null) {
return;
}
//第一次获取根
str.append(root.val);
str.append(",");
serialize(root.left, str);
serialize(root.right, str);
}
根据二分查找思想和（递归萌芽-调用者模式思想），重建二叉树：
//【根据前序遍历】重建二叉树
public TreeNode deserialize(String data) {
//String类型数据
if (data == null || data.length() == 0) {
return null;
}
//将字符串转换为String数组
String[] nodes = data.split(",");
//重建二叉树
return deserialize(nodes, 0, nodes.length - 1);
}
//递归调用(根据一个前序数组重建二叉树)
public TreeNode deserialize(String[] nodes, int left, int right) {
if (left > right) {
return null; //左边大于右边，直接返回null
}
//最左为根节点
TreeNode root = new TreeNode(Integer.valueOf(nodes[left]));
//左右子树长度确定，数组元素直到大于根
boolean flag = false;
int count = left + 1;
//right是下标，而不是数组长度(易错点01)
for (int i = count; i < right + 1; i++) {
//没有考虑--不会进这个判断的情况。
if (Integer.valueOf(nodes[i]) > Integer.valueOf(nodes[left])) {
count = i;
flag = true;
break;
}
}
if (flag) {
//找到元素
root.left = deserialize(nodes, left + 1, count - 1);
root.right = deserialize(nodes, count, right);
} else {
//未找到右子树
root.left = deserialize(nodes, left + 1, right);
}
return root;
}
根节点调用自身方法，不会关注内部实现逻辑。而是为了得到左子树以及右子树。
2. 二叉树的序列化和反序列化
使用层次遍历，遍历二叉树，注意，若是二叉树的子节点为
null的话，那么字符串插入null。
序列化二叉树：
//层次遍历二叉树
public String Serialize(TreeNode root) {
if (root == null) {
return null;
}
StringBuilder sb = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root); //根元素进队列
//以队列驱动数量
while (queue.size() != 0) {
TreeNode treeNode = queue.poll(); //根元素先出队列
if (treeNode == null) {
sb.append("null,");
continue;
}
sb.append(treeNode.val);
sb.append(",");
//将节点保存到队列中
queue.add(treeNode.left);
queue.add(treeNode.right);
}
String s = sb.toString();
if (s.endsWith(",")) {
s = sb.substring(0, s.length() - 1);
}
return s;
}
反序列化二叉树：
根据层次遍历的结果，重建二叉树。
首先，我们可以获取到根节点。我们需要借助ArrayList数组保存节点信息，在节点重构完左右两节点后。指向下一个节点。【父节点一边构造子节点，一边将子节点保存到ArrayList中。】
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) {
return null;
}
String[] strings = data.split(",");
//重建二叉树，借助数组；
ArrayList<TreeNode> link = new ArrayList<>();
//将第一个元素放进去
TreeNode root = new TreeNode(Integer.valueOf(strings[0]));
link.add(root);
//判断该节点是不是左节点
boolean isLeft = true;
int index = 0;
for (int i = 1; i < strings.length; i++) {
if (!"null".equals(strings[i])) {
//创建新节点
TreeNode treeNode = new TreeNode(Integer.valueOf(strings[i]));
if (isLeft) {
link.get(index).left = treeNode;
} else {
link.get(index).right = treeNode;
}
link.add(treeNode); //将新节点保存进去
}
if (isLeft == false) {
index++; //赋予完右节点，才开始下一个元素
}
isLeft = !isLeft; //每寻找一个节点，那么标志变换一次
}
return root;
}
