LeetCode刷题-设计问题-二叉树的序列化与反序列化
文章目录
问题:
序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例:
你可以将以下二叉树:
1
/ \
2 3
/ \\
4 5
序列化为 "[1,2,3,null,null,4,5]"
序列化思路:
首先看到二叉树首先想到的是它的前、中、后序遍历。
利用前序遍历,我们需要做的是分辨每个节点及节点左子树右子树的值,首先需要在遍历获得值后面加上分隔号“!”,然后当为空值时需要用“#!”来表示。
代码:
public String serialize(TreeNode root) {
if(root==null){
return"#!";
}
String str=root.val+"!";
str+=serialize(root.left);
str+=serialize(root.right);
return str;
}
反序列化思路:
首先要将序列化的字符串根据“!”间隔分开变成对应的字符串数组;
由于放入队列中更好操作(poll),将数组值导入LinkedLiset中;
然后按照先序排列的顺序还原二叉树即可。
代码:
public TreeNode deserialize(String data) {
String[] nodeNum =data.split("!");
Queue<String> numList=new LinkedList<String>();
for (int i=0;i<nodeNum.length;i++){
numList.offer(nodeNum[i]);
}
return rebuild(numList);
}
public TreeNode rebuild(Queue<String> numList){
String value=numList.poll();
if (value.equals("#")) {
return null;
}
TreeNode head=new TreeNode(Integer.valueOf(value));
head.left=rebuild(numList);
head.right=rebuild(numList);
return head;
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论