大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

首先要明白题意：

  • 序列化：把内存中的二叉搜索树转成字符串；
  • 反序列化：把字符串恢复成内存中的二叉搜索树。

题目没有限定我们用什么方法，只要求我们序列化后的字符串尽可能紧凑。

解法不固定，只要序列化后的结果，能被反序列化函数还原成一模一样的二叉搜索树（BST），都认为是正确答案。

评测的过程是下面这样：

  1. Codec ser = new Codec();
  2. Codec deser = new Codec();
  3. String tree = ser.serialize(root);
  4. TreeNode ans = deser.deserialize(tree);
  5. return ans;

解题方法

前序遍历 + 递归

BST 的基本定义：

  • BST 的左子树所有节点都比根节点值小，右子树所有节点都比根节点值大。

只知道树的一种遍历方式，是没法确定这个树的，BST 也不例外。

因此，我的主要思路就是：采用前序遍历的序列化 BST，再根据 BST 的性质进行反序列化。

具体做法如下：

  • 前序遍历得到的数组的第一个值就是 BST 的根节点
  • 数组后面的这些数中比根节点的值小的是根节点的左子树，比根节点值大的是根节点的右子树
  • 递归就可以反序列化出原本的 BST

代码如下：

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Codec:
  10.     def serialize(self, root):
  11.         vals = []
  12.         def preOrder(root):
  13.             if root:
  14.                 vals.append(root.val)
  15.                 preOrder(root.left)
  16.                 preOrder(root.right)
  17.         preOrder(root)
  18.         return ','.join(map(str, vals))
  21.     def deserialize(self, data):
  22.         if not data or data == '':
  23.             return None
  24.         vals = map(int, data.split(","))
  25.         root = TreeNode(vals[0])
  26.         leftVals = [x for x in vals if x < vals[0]]
  27.         rightVals = [x for x in vals if x > vals[0]]
  28.         root.left = self.deserialize(",".join(map(str, leftVals)))
  29.         root.right = self.deserialize(",".join(map(str, rightVals)))
  30.         return root
  33. # Your Codec object will be instantiated and called as such:
  34. # ser = Codec()
  35. # deser = Codec()
  36. # tree = ser.serialize(root)
  37. # ans = deser.deserialize(tree)
  38. # return ans

复杂度

  • 时间复杂度：序列化是 $O(N)$；反序列化最差达到 $O(N^2)$，因为当树的节点都偏向于一侧的时候，每遍历一个节点，都要对访问剩余的 449. 序列化和反序列化二叉搜索树 - 图1个节点。
  • 空间复杂度：序列化是 $O(N)$；反序列化最差达到 $O(N^2)$，理由同上。

    总结

  1. 没有固定套路的题目，需要自己发掘数据结构的性质，找到合适的解法。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。