记录生活中的点点滴滴

0%

二叉树的序列化与反序列化

昨天刷了一些链表相关的题目,今天又刷了一些二叉树的题目,我很大的感触就是链表加递归,再加上你自己的逻辑。

先记录一下 二叉树的序列化与反序列化 这道题,因为感觉这道题有很多重要的逻辑思想,掌握了这些,刷其他题也就不会那么迷茫。

OK,不多bb,直接上题目。

题目要求

再看看二叉树基本的节点结构代码:

1
2
3
4
5
6
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}

OK,下面我们思考一下如何解决序列化的问题,序列化无非就是保存二叉树的节点val值到字符串中,其实就是二叉树的遍历。

好的,前序遍历、中序遍历、后序遍历,还有层次遍历(借助队列这一数据结构),但是我们都知道:

给定一棵树的前序遍历和中序遍历或给定中序遍历和后序遍历即可还原出整棵树。有些老师还会提到如果只是给出前序遍历和后续遍历则不可以。

为什么一种遍历方式不能确定?

因为我们这样的遍历是不存储空的节点的,只按照顺序把val值排了顺序。

对于这道题,我们也没必要搞的那么复杂,我们只要把空的节点也进行保存即可,这样只需要一种遍历方式就可以了。

但是注意的是,这样的话,中序遍历是不行的。为什么?举个例子吧。

其实还有就是,我们每个节点之间还得需要一个分隔符,不然有的值可能位数比较大,就容易出错。

所以我们先定义null符和分隔符,便于后续使用:

1
2
3
4
// 空指针字符
String NULL = "#";
// 分割字符
String SEP = ",";

行吧,下面我们进行三种方法的编写:前序遍历、后序遍历、层次遍历

前序遍历

我们前面已经分析过了,把遍历结果存到字符串中,肯定需要一个 StringBuilder 对象,注意不同的节点要对应不同的操作方法。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
preTravese(root,sb);
return sb.toString();
}
//前序遍历
public void preTravese(TreeNode root,StringBuilder sb){
if(root==null){
sb.append(NULL).append(SEP);
return;
}
sb.append(root.val).append(SEP);
preTravese(root.left,sb);
preTravese(root.right,sb);
}

很容易理解,但是怎样反序列化回去呢?

首先我们得先把字符串进行 split(SEP),然后得到的数组最好放到一个LinkedList中。

然后肯定要使用递归进行解决,我们定义一个函数 TreeNode preTravese2(LinkedList<String> nodes)

假设这个函数就是传入一个LinkedList,然后返回由它构造的二叉树。

那么这个函数里面怎样编写呢?

首先我们从根节点开始,它肯定得把这个LinkedList进行 removeFirst,然后得到的值进行 Integer.pareseInt() 构建一个二叉树节点。接下来它的左节点就等于递归遍历这个list,右节点等于递归遍历这个list。

所以base case呢?肯定是需要知道如果 removeFirst() 的值是空的话,要返回,什么都不做。这样先左节点等于递归遍历这个list才会结束,接下来的就到了右节点等于接着递归遍历这个list。

所以,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public TreeNode deserialize(String data) {
LinkedList<String> nodes = new LinkedList<>();
for(String s : data.split(SEP))
nodes.add(s);
return preTravese2(nodes);
}
//前序遍历还原链表
public TreeNode preTravese2(LinkedList<String> nodes){
if(nodes.isEmpty()) return null;
String s = nodes.removeFirst();
if(NULL.equals(s)){//遇空判断
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(s));
root.left = preTravese2(nodes);
root.right = preTravese2(nodes);
return root;
}

后序遍历

后序遍历进行序列化与前序遍历很相似,只是需要修改一下顺序即可。不多bb,直接代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
preTravese(root,sb);
return sb.toString();
}
//后序遍历
public void preTravese(TreeNode root,StringBuilder sb){
if(root==null){
sb.append(NULL).append(SEP);
return;
}
preTravese(root.left,sb);
preTravese(root.right,sb);
sb.append(root.val).append(SEP);
}

然后想想反序列化,前序的话我们是从前面开始的,为什么从前面?因为根节点就是前面第一个的节点,然后left,right。

同理,那么后续遍历呢?

不能从前面开始了,要从后面开始了。逻辑什么的还是和前序一样,从后面开始,那么就是right,left。

好的,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public TreeNode deserialize(String data) {
LinkedList<String> nodes = new LinkedList<>();
for(String s : data.split(SEP))
nodes.add(s);
return preTravese2(nodes);
}
//后序遍历还原链表
public TreeNode preTravese2(LinkedList<String> nodes){
if(nodes.isEmpty()) return null;
String s = nodes.removeLast();
if(NULL.equals(s)){//遇空判断
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(s));

root.right = preTravese2(nodes);
root.left = preTravese2(nodes);
return root;
}

层次遍历

层次遍历需要借助队列这一数据结构。

先需要将根节点入队,判断队列是否为空进行循环,里面将首元素出队,将它的左右节点入队,不过要注意对空节点的处理。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public String serialize(TreeNode root) {
if(root==null) return "";
//层次遍历序列化二叉树,利用队列
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
StringBuilder sb = new StringBuilder();
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(node==null){
sb.append(NULL).append(SEP);
continue;
}
sb.append(node.val).append(SEP);
queue.offer(node.left);
queue.offer(node.right);
}
return sb.toString();
}

那么怎样进行反序列化呢?

首先得到一个字符串数组,接着就需要将0位置的构造成根节点,并加入队列,然后i从1开始进行for循环数组,每个for循环中判断连续两个i位置的值,和队列一起使用,判断左右节点。

好的,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public TreeNode deserialize(String data) {
if(data==null || data.isEmpty()) return null;
String[] nodes = data.split(SEP);
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
queue.offer(root);
for(int i=1;i<nodes.length;i++){
TreeNode node = queue.poll();
if(!NULL.equals(nodes[i])){
node.left = new TreeNode(Integer.parseInt(nodes[i]));
queue.offer(node.left);
}else{
node.left = null;
}
if(!NULL.equals(nodes[++i])){
node.right = new TreeNode(Integer.parseInt(nodes[i]));
queue.offer(node.right);
}else{
node.right = null;
}
}
return root;
}