题目描述
序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
样例
你可以将以下二叉树:
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
提示: 这与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。
说明: 不要使用类的成员 / 全局 / 静态变量来存储状态,你的序列化和反序列化算法应该是无状态的。
算法分析
-
序列化:对整个二叉树进行先序遍历的序列存起来,同时需要把每个结点的空节点使用
"#"
进行标记,例如样例的顺序是1,2,#,#,3,4,#,#,5,#,#
-
反序列化:对整个字符串按照
","
进行分割,把所有的元素按序存到链表中(链表元素的顺序是先序序列),按先序遍历的方式拿链表的元素,每次拿第一个元素作为根结点,并删除链表中的第一个元素,然后递归到左儿子做同样的操作,递归到右儿子做同样的操作。注意:若第一个元素是"#"
,表示该节点是null
,直接返回null
时间复杂度 $O(n)$
Java 代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
//根据先序遍历的顺序,每次只拿第一元素作为根
static TreeNode dfs(List<String> list)
{
if(list.get(0).equals("#"))
{
list.remove(0);
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(list.get(0)));
list.remove(0);
root.left = dfs(list);
root.right = dfs(list);
return root;
}
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null)
return "#";
return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] s = data.split(",");
List<String> list = new ArrayList<String>(Arrays.asList(s));
return dfs(list);
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));