Loger's blog site

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

0%

好友抖音面试真题:二叉树的序列化与反序列化(解法二)

前言

之前分享了朋友面试抖音的真题:LeetCode 297. 二叉树的序列化与反序列化,我用的BFS(广度优先遍历)的方法来做的。事实上,朋友在面试的时候也是用BFS来做的。

BFS的解法点击跳转:好友抖音面试真题:297.二叉树的序列化与反序列化

BFS的运行结果其实不算很满意,所以今天我又用DFS(深度优先遍历)来重新做了一遍,两种方法的耗时对比:

可以看出,DFS是要比BFS快不少的,所以分享下DFS的解法。

题目

还是先看看题目:

前序遍历

这里就不赘述了,直接上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private void ser(StringBuilder sb, TreeNode root) {
if (root == null) {
sb.append("nil,");
return;
}
sb.append(root.val).append(",");
ser(sb, root.left);
ser(sb, root.right);
}

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
ser(sb, root);
return sb.substring(0, sb.length() - 1);
}

这里碰到为空的情况,需要把结果拼接成nil,好让重构二叉树的时候可以知道哪些节点是没有左右孩子的。

反序列化

题目所给的那棵树序列化:

前序遍历是先 根,然后左右。那么重建的时候也是先根后左右:

  1. build(1) // root节点
  2. 开始考虑root的左孩子:build(2)
  3. 开始考虑2的左孩子:build(nil) // 碰到nil就没了。然后考虑2的右孩子,也是nil。到这里这条路径就结束了
  4. root节点的左孩子考虑完之后,要开始考虑root的右孩子了:build(3)
  5. 然后再考虑3的左孩子:build(4); 3的右孩子:build(5)
  6. 以此类推。

说白了,其实跟前序遍历的递归过程是一样的。

所以直接上代码去感受下:

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
private TreeNode des(LinkedList<String> strings) {
// 依次取出每一个元素
String poll = strings.poll();
// 如果没有了或者 为nil,那么返回 null
if (poll == null || "nil".equals(poll)) {
return null;
}
// 构建当前节点
TreeNode root = new TreeNode(Integer.parseInt(poll));
// 构建当前节点的左孩子
root.left = des(strings);
// 构建当前节点的右孩子
root.right = des(strings);
// 把当前节点返回出去。(返回出去就变成了它上一个节点的左右孩子了/或者本身就是root节点)
return root;
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.isEmpty()) {
return null;
}
LinkedList<String> strings = new LinkedList<>(Arrays.asList(data.split(",")));
return des(strings);
}

总结

递归是一个比较抽象的东西,也很难给讲得透彻。所以对于这种做法,还是需要多琢磨。琢磨透了,下次做题也还是不会,hahaha~

谢绝转载

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