Serialize and Deserialize Binary Tree
首先，很抱歉，停更了几天。因为生病了，烧到了39度，喉咙疼的要命，不知道是不是跟北京最近的雾霾天气有关。现在好一些了，从今天起恢复更新。
今天是一道有关二叉树的题目，来自LeetCode，难度为Medium，Acceptance为24.6%。
题目如下
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.
For example, you may serialize the following tree
1
/ \
2 3
/ \
4 5
as [1,2,3,null,null,4,5], just the same as how LeetCode OJ 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.
解题思路及代码见阅读原文
回复0000查看更多题目
解题思路
首先，老规矩，看到二叉树，想到二叉树的三种遍历方式。
然后，这里需要序列化和反序列化二叉树，可以采用的方法很多了。多种遍历方式都可以，只有在序列化和反序列化时采用相同的遍历方式即可。其中较为简单的是前序遍历和层次遍历。
因为采用层次遍历行需要利用队列，会多引入一种数据结构，所以这里采用前序遍历，这种方法也比较容易理解和实现。
序列化，即将二叉树转成字符串。因为二叉树中包含
null节点。需要采用一个特殊字符标记，因为这里的二叉树的值都是数字，所以可以采用非数字作为标记，如采用X。每个节点间用,分割。然后就是按照前序遍历的方法，输入二叉树成字符串，较为简单，不再赘述。反序列化，即将刚才生成的字符串转换成二叉树。首先，将字符串按照
,split成字符串数组的形式，该数组中每一个元素即为一个二叉树的节点。
这里本来可以很简单的用一个全局变量记录，当前遍历的数组index，但是因为题目中要求采用stateless的方式，所以必须换种方式。
可以采用List的方式，将已经遍历的节点删除，剩下的就是当该字符串不是X时，按照前序遍历的方式重建二叉树。
代码如下
Java版
public class Codec {
private static final String spliter = ",";
private static final String NN = "X";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
buildString(root, sb);
return sb.toString();
}
private void buildString(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append(NN).append(spliter);
} else {
sb.append(node.val).append(spliter);
buildString(node.left, sb);
buildString(node.right,sb);
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Deque<String> nodes = new LinkedList<>();
nodes.addAll(Arrays.asList(data.split(spliter)));
return buildTree(nodes);
}
private TreeNode buildTree(Deque<String> nodes) {
String val = nodes.remove();
if (val.equals(NN)) return null;
else {
TreeNode node = new TreeNode(Integer.valueOf(val));
node.left = buildTree(nodes);
node.right = buildTree(nodes);
return node;
}
}
}
关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助
