Loger's blog site

Loger's blog site,分享编程知识,顺便发发牢骚

0%

好友抖音面试真题:297.二叉树的序列化与反序列化

好友抖音面试

前段时间,好朋友Hellovass参加抖音的面试(高级Android开发工程师)。按照字节的惯例,手撸算法是跑不了的。首先在这里祝好朋友在抖音一切顺利,事事顺心。

题目

终于有心思静下心来搞点事情了,第一件事就是先回顾下好友的面试真题:LeetCode第297题——《二叉树的序列化与反序列化》。

这是一道难度为Hard的题目,其实如果熟悉二叉树的BFS和DFS的话,思路应该会是比较水到渠成的。

题目分析

回到这个题目,题意是你怎么把二叉树变成”一串字符串”,然后又怎么通过字符串重组回一颗二叉树。首先要序列化一颗二叉树,首先肯定要遍历树的各个节点吧:有DFS(深度优先遍历)和BFS(广度优先遍历)。这个题我最开始的想法就是BFS,因为递归是比较抽象的(本人水平有限,所以就抽象了),所以我不会第一时间就往递归上面去想。

假设一棵树:

1
2
3
  2
/ \
1 3

BFS的结果是:

1
2,1,3

由 2,1,3 怎么重建二叉树呢,不难发现,我们先把根节点2拿出去,剩下的1和3就分别是2的左右孩子了。

假设这棵树再大一点:(题目那颗)

1
2
3
4
5
  1
/ \
2 3
/ \
4 5

BFS的结果是:

1
1,2,3,4,5

根据上面的思想,先把root节点拿出来,取后面的两个分别作为左右孩子:

1
2
3
  1
/ \
2 3

这里没问题,继续为2找左右孩子,这时候就取到4,5了,变成:

1
2
3
4
5
    1
/ \
2 3
/ \
4 5

这里显然就不对了。其实题目已经给了tips:

用上面的思想,按照:

1
1,2,3,null,null,4,5

来重建二叉树,就没有问题了。

那么思路就很清晰了,思路清晰也不代表代码好写,这是两码事;写完代码也不见得所有的test case都能pass。

代码实现

先把序列化的写了,比较传统的BFS,碰到左右子树为空的则输出为nil字符串,这里任意能区分的字符即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "nil";
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
StringBuilder sb = new StringBuilder();
while (!queue.isEmpty()) {
TreeNode poll = queue.remove();
if (poll == null) {
sb.append("nil").append(",");
continue;
}
sb.append(poll.val).append(",");
queue.add(poll.left);
queue.add(poll.right);
}
return sb.substring(0, sb.length() - 1);
}

反序列化的代码,也是要用到一个队列,跟遍历一样,先把root节点放到队列中,然后不断地循环,把需要找左右孩子的节点继续放入到队列中去:(通过代码注释来讲解)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.isBlank()) {
return null;
}
String[] split = data.split(",");
// 这里不要忘记了判断第一个结果就是空的情况,本人在这里提交了几遍才找出问题
if ("nil".equals(split[0])) {
return null;
}
// 先把root节点放到queue里面去
TreeNode root = new TreeNode(Integer.parseInt(split[0]));
// index就是你要开始找的孩子节点的位置了。
// 第二、三个节点肯定是root节点的左右孩子;
// 然后以此类推:四、五 节点一定是二号节点的左右孩子
int index = 1;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);

while (!queue.isEmpty()) {
// 从队列里拿出一个节点,然后找它的左右孩子
TreeNode node = queue.remove();
// 左孩子就是当前index的位置
String v1 = split[index++];
// 左孩子
if (!"nil".equals(v1)) {
node.left = new TreeNode(Integer.parseInt(v1));
queue.add(node.left);
}
// 右孩子
String v2 = split[index++];
if (!"nil".equals(v2)) {
node.right = new TreeNode(Integer.parseInt(v2));
queue.add(node.right);
}
}

return root;
}

运行结果

写完放到LeetCode上跑一下看看:

击败数并不高,说明还有更好的写法。但是如果你是面试,其实到这里就已经没有问题了。当然学习不全是为了面试,要不然就真的太累了,希望大家都能找到个好公司,节日福利多多的那种。

谢绝转载

【Happyjava】原创文章,未经允许,谢绝转载!