题目描述
序列化是将数据结构或对象转换为一系列位的过程,以便它可以存储在文件或内存缓冲区中,或通过网络连接链路传输,以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串,并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
样例
输入:root = [2,1,3]
输出:[2,1,3]
输入:root = []
输出:[]
提示:
- 树中节点数范围是
[0, 10^4]
0 <= Node.val <= 10^4
- 题目数据 保证 输入的树是一棵二叉搜索树。
算法分析
该题也可以用 LeetCode 297.二叉树的序列化与反序列化的解法
下面题解是使用了二叉搜索树的特性(中序遍历是有序的)解决
-
序列化:对整个二叉树进行先序遍历的序列存起来,同时需要把每个结点的空节点使用
"#"
进行标记,例如图中的顺序是
2,1,#,#,4,3,#,#,5,#,#
-
反序列化:先把字符串中对应的所有数字都扣到一个链表中,即将样例扣成
2 1 4 3 5
,存到链表中,dfs(List<Integer> s, int l, int r)
的作用是在链表中[l, r]
的区间形成一棵树后并返回根节点,根据先序遍历和中序遍历构造出一棵唯一的树的原理- 1、将
[l, r]
区间中第一个元素s[l]
作为根结点,该值是p
- 2、在
[l, r]
区间中找到小于p
的区间,递归构造出左子树 - 3、在
[l, r]
区间中找到大于p
的区间,递归构造出右子树
- 1、将
时间复杂度 $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<Integer> s, int l, int r)
{
if(l > r) return null;
//选取第一个为根结点
TreeNode root = new TreeNode(s.get(l));
//找到第一个比root.val大的元素的位置
int idx = l + 1, p = s.get(l);
while(idx <= r && s.get(idx) < p) idx ++;
root.left = dfs(s, l + 1, idx - 1);
root.right = dfs(s, idx, r);
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) {
//把data的所有数字筛出来存到s链表中
String[] s1 = data.split(",");
List<Integer> s = new ArrayList<Integer>();
for(int i = 0;i < s1.length;i ++)
{
if(s1[i].equals("#")) continue;
s.add(Integer.parseInt(s1[i]));
}
return dfs(s, 0, s.size() - 1);
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;