今天要给大家分享的是关于二叉树的序列化与反序列化问题。请实现两个函数，分别用来序列化和反序列化二叉树，包含了具体的代码实现和思路。
二叉树的序列化：将一棵二叉树根据某一种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树能够长久保存。
序列化能够基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点(#)，以 ! 代表着一个结点值的结束(value!)。
二叉树的反序列化：依据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
思路1：
//采用层序遍历，不需要将转化为完全二叉树的简单方法
public class Solution
{
String Serialize(TreeNode root)
{
StringBuilder sb = new StringBuilder();
Queue < TreeNode > queue = new LinkedList < TreeNode > ();
if (root != null)
queue.add(root);
while (!queue.isEmpty())
{
TreeNode node = queue.poll();
if (node != null)
{
queue.offer(node.left);
queue.offer(node.right);
sb.append(node.val + ",");
}
else
{
sb.append("#" + ",");
}
}
if (sb.length() != 0)
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
TreeNode Deserialize(String str)
{
TreeNode head = null;
if (str == null || str.length() == 0)
return head;
String[] nodes = str.split(",");
TreeNode[] treeNodes = new TreeNode[nodes.length];
for (int i = 0; i < nodes.length; i++)
{
if (!nodes[i].equals("#"))
treeNodes[i] = new TreeNode(Integer.valueOf(nodes[i]));
}
for (int i = 0, j = 1; j < treeNodes.length; i++)
{
if (treeNodes[i] != null)
{
treeNodes[i].left = treeNodes[j++];
treeNodes[i].right = treeNodes[j++];
}
}
return treeNodes[0];
}
}
//前序遍历
public class Solution
{
String Serialize(TreeNode root)
{
StringBuilder sb = new StringBuilder();
getSerializeString(root, sb);
if (sb.length() != 0)
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
getSerializeString(TreeNode root, StringBuilder sb)
{
if (root == null)
sb.append("#,");
else
{
sb.append(root.val + ",");
getSerializeString(root.left, sb);
getSerializeString(root.right, sb);
}
}
TreeNode Deserialize(String str)
{
if (str == null || str.length() == 0 || str.length() == 1)
return null;
String[] nodes = str.split(",");
TreeNode[] treeNodes = new TreeNode[nodes.length];
for (int i = 0; i < nodes.length; i++)
{
if (!nodes[i].equals("#"))
treeNodes[i] = new TreeNode(Integer.valueOf(nodes[i]));
}
Stack < TreeNode > stack = new Stack < > ();
stack.push(treeNodes[0]);
int i = 1;
while (treeNodes[i] != null)
{
stack.peek()
.left = treeNodes[i];
stack.push(treeNodes[i++]);
}
while (!stack.isEmpty())
{
stack.pop()
.right = treeNodes[++i];
if (treeNodes[i] != null)
{
stack.push(treeNodes[i++]);
while (treeNodes[i] != null)
{
stack.peek()
.left = treeNodes[i];
stack.push(treeNodes[i++]);
}
}
}
return treeNodes[0];
}
}思路2：
public class Solution
{
public int index = -1;
String Serialize(TreeNode root)
{
StringBuilder s = new StringBuilder();
if (root == null)
{
s.append("#,");
return s.toString();
}
s.append(root.val + ",");
s.append(Serialize(root.left));
s.append(Serialize(root.right));
return s.toString();
}
TreeNode Deserialize(String str)
{
index++;
int len = str.length();
if (index >= len)
{
return null;
}
String[] DLRseq = str.split(",");
TreeNode leave = null;
if (!DLRseq[index].equals("#"))
{
leave = new TreeNode(Integer.valueOf(DLRseq[index]));
leave.left = Deserialize(str);
leave.right = Deserialize(str);
}
return leave;
}
}思路3：
我们知道，通过一棵二叉树的前序遍历序列和中序遍历序列可以还原一棵树，所以此题如果使用这种方式则明显可解。只是问题在于，在反序列化的时候需要全部读出序列化串后才能还原。
于是我们可以采用层次遍历的方式序列化一棵树，在节点为null的时候使用#作为占位，因为反序列化的时候需要使用串的索引来确定父节点的子节点，
也就是说我们需要将一棵树序列化成一棵完全二叉树，空节点使用#作为占位。
public class Serialize
{
String Serialize(TreeNode root)
{
if (root == null)
{
return null;
}
StringBuffer sb = new StringBuffer();
ArrayList < TreeNode > list = new ArrayList < TreeNode > ();
int count = (1 << treeDepth(root)) - 1; //计数，拿到此树的深度后计算对应完全二叉树节点数
list.add(root);
count--;
TreeNode tmpNode = null;
//层次遍历二叉树，开始序列化
while (list.size() > 0 && count >= 0)
{
tmpNode = list.remove(0);
if (tmpNode != null)
{
sb.append(tmpNode.val + ",");
list.add(tmpNode.left);
list.add(tmpNode.right);
}
else
{
sb.append("#,"); //#作为空节点占位符
list.add(null);
list.add(null);
}
count--;
}
return sb.toString();
}
TreeNode Deserialize(String str)
{
if (str == null || str.length() == 0)
{
return null;
}
return Deserialize(str.split(","), 0);
}
TreeNode Deserialize(String[] strings, int index)
{
TreeNode newNode = null;
if (index < strings.length)
{
if (!strings[index].equals("#"))
{
newNode = new TreeNode(Integer.parseInt(strings[index]));
newNode.left = Deserialize(strings, 2 * index + 1);
newNode.right = Deserialize(strings, 2 * index + 2);
}
}
return newNode;
}
int treeDepth(TreeNode root)
{
int depth = 0;
if (root == null)
{
return depth;
}
else
{
int lDepth = treeDepth(root.left) + 1;
int rDepth = treeDepth(root.right) + 1;
return lDepth > rDepth ? lDepth : rDepth;
}
}
}以上三种实现方法和具体思路大家都了解了吗？更多JAVA实例，可以继续关注本站了解。