LC 449. 序列化和反序列化二叉搜索树

题目描述

这是 LeetCode 上的 449. 序列化和反序列化二叉搜索树 ,难度为 中等

序列化是将数据结构或对象转换为一系列位的过程,以便它可以存储在文件或内存缓冲区中,或通过网络连接链路传输,以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串,并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

示例 1:

1
2
3
输入:root = [2,1,3]

输出:[2,1,3]

示例 2:
1
2
3
输入:root = []

输出:[]

提示:

  • 树中节点数范围是 $[0, 10^4]$
  • $0 <= Node.val <= 10^4$
  • 题目数据 保证 输入的树是一棵二叉搜索树。

BST 特性(前序遍历)

实现上,我们可以忽略「BST」这一条件,使用「BFS」或者「直接充当满二叉树」来序列化和反序列化。

但由于点的数量是 $1e4$,最坏情况下是当 BST 成链时,会有较大的空间浪费。

因此,一种较为紧凑的序列化/反序列化的方式是利用「前序遍历 + BST 特性」:

  • 序列化:对 BST 进行「前序遍历」,并跳过空节点,节点值通过 , 进行分割,假设最终序列化出来的字符串是 s
    之所以使用「前序遍历」是为了方便反序列化:首先对于某个子树而言,其必然是连续存储,也就是必然能够使用 $s[l,r]$ 所表示处理,同时首位元素必然是该子树的头结点;

  • 反序列化:将 s 根据分隔符 , 进行分割,假设分割后数组 ss 长度为 $n$,那么 $ss[0, n - 1]$ 代表完整的子树,我们可以利用「二叉树」特性递归构建,设计递归函数 TreeNode dfs2(int l, int r, Sring[] ss),其含义为利用 $ss[l, r]$ 连续段构造二叉树,并返回头结点:

    1. $ss[l]$ 为头结点,其值为 $t$,在 $[l, r]$ 范围内找到第一个比 $t$ 大的位置 $j$:
    2. $ss[l]$ 的左子树的所有值均比 $t$ 小,且在 s 中连续存储,我们可以递归处理 $[l + 1, j - 1]$ 构建左子树;
    3. $ss[l]$ 的右子树的所有值均比 $t$ 大,且在 s 中连续存储,我们可以递归处理 $[j, r]$ 构建右子树。

代码:

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
public class Codec {
public String serialize(TreeNode root) {
if (root == null) return null;
List<String> list = new ArrayList<>();
dfs1(root, list);
int n = list.size();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(list.get(i));
if (i != n - 1) sb.append(",");
}
return sb.toString();
}
void dfs1(TreeNode root, List<String> list) {
if (root == null) return ;
list.add(String.valueOf(root.val));
dfs1(root.left, list);
dfs1(root.right, list);
}
public TreeNode deserialize(String s) {
if (s == null) return null;
String[] ss = s.split(",");
return dfs2(0, ss.length - 1, ss);
}
TreeNode dfs2(int l, int r, String[] ss) {
if (l > r) return null;
int j = l + 1, t = Integer.parseInt(ss[l]);
TreeNode ans = new TreeNode(t);
while (j <= r && Integer.parseInt(ss[j]) <= t) j++;
ans.left = dfs2(l + 1, j - 1, ss);
ans.right = dfs2(j, r, ss);
return ans;
}
}

  • 时间复杂度:令节点数量为 $n$,序列化的复杂度为 $O(n)$;反序列时由于存在「找第一个比头结点值大的位置」操作,每个节点可能被扫描多次,扫描次数与当前节点所在的深度相关,最坏情况下为一条往左下方的链,复杂度为 $O(n^2)$
  • 空间复杂度:$O(n)$

二分优化

在解法一中的「反序列操作」操作的瓶颈在于需要「找第一个比头结点值大的位置」。

假设连续段 $s[l, r]$ 代表某棵子树的话,由于我们是采用「前序遍历」的方式生成 s,因此头结点必然是 $s[l]$,而对于头结点的左右子树,必然是连续两段(先左再右)的形式存储在 $[l + 1, r]$ 中,同时由于该子树是 BST,因此这连续两段必然满足「前一段(左子树)小于 $t$」和「后一段(右子树)大于 $t$」。

即具有「二段性」,因此「找第一个比头结点值大的位置」可用「二分」实现。

代码:

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
public class Codec {
public String serialize(TreeNode root) {
if (root == null) return null;
List<String> list = new ArrayList<>();
dfs1(root, list);
int n = list.size();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(list.get(i));
if (i != n - 1) sb.append(",");
}
return sb.toString();
}
void dfs1(TreeNode root, List<String> list) {
if (root == null) return ;
list.add(String.valueOf(root.val));
dfs1(root.left, list);
dfs1(root.right, list);
}
public TreeNode deserialize(String s) {
if (s == null) return null;
String[] ss = s.split(",");
return dfs2(0, ss.length - 1, ss);
}
TreeNode dfs2(int l, int r, String[] ss) {
if (l > r) return null;
int ll = l + 1, rr = r, t = Integer.parseInt(ss[l]);
while (ll < rr) {
int mid = ll + rr >> 1;
if (Integer.parseInt(ss[mid]) > t) rr = mid;
else ll = mid + 1;
}
if (Integer.parseInt(ss[rr]) <= t) rr++;
TreeNode ans = new TreeNode(t);
ans.left = dfs2(l + 1, rr - 1, ss);
ans.right = dfs2(rr, r, ss);
return ans;
}
}

  • 时间复杂度:令节点数量为 $n$,序列化的复杂度为 $O(n)$;反序列时由于存在「找第一个比头结点值大的位置」操作,最坏情况下为一条往左下方的链,该操作采用「二分」,复杂度为 $O(\log{n})$,整体复杂度为 $O(n\log{n})$
  • 空间复杂度:$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.449 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!