我们先来看题目描述序列化是将数据结构或对象转换为一系列位的过程以便它可以存储在文件或内存缓冲区中或通过网络连接链路传输以便稍后在同一个或另一个计算机环境中重建。设计一个算法来序列化和反序列化 二叉搜索树。对序列化/反序列化算法的工作方式没有限制。您只需确保二叉搜索树可以序列化为字符串并且可以将该字符串反序列化为最初的二叉搜索树。编码的字符串应尽可能紧凑。示例 1输入root [2,1,3] 输出[2,1,3]示例 2输入root [] 输出[]提示树中节点数范围是 [0, 10*4]0 Node.val 10*4题目数据 保证 输入的树是一棵二叉搜索树。解决方案二叉搜索树是一种特殊的二叉树序列化和反序列化过程也可以参照「297. 二叉树的序列化与反序列化」的过程。二叉搜索树的特殊之处在于其中序遍历是有序的可以利用这一点来优化时间和空间复杂度。方法后序遍历思路给定一棵二叉树的「先序遍历」和「中序遍历」可以恢复这颗二叉树。给定一棵二叉树的「后序遍历」和「中序遍历」也可以恢复这颗二叉树。而对于二叉搜索树给定「先序遍历」或者「后序遍历」对其经过排序即可得到「中序遍历」。因此仅对二叉搜索树做「先序遍历」或者「后序遍历」即可达到序列化和反序列化的要求。此题解采用「后序遍历」的方法。序列化时只需要对二叉搜索树进行后序遍历再将数组编码成字符串即可。反序列化时需要先将字符串解码成后序遍历的数组。在将后序遍历的数组恢复成二叉搜索树时不需要先排序得到中序遍历的数组再根据中序和后序遍历的数组来恢复二叉树而可以根据有序性直接由后序遍历的数组恢复二叉搜索树。后序遍历得到的数组中根结点的值位于数组末尾左子树的节点均小于根节点的值右子树的节点均大于根节点的值可以根据这些性质设计递归函数恢复二叉搜索树。代码Python3class Codec: def serialize(self, root: TreeNode) - str: arr [] def postOrder(root: TreeNode) - None: if root is None: return postOrder(root.left) postOrder(root.right) arr.append(root.val) postOrder(root) return .join(map(str, arr)) def deserialize(self, data: str) - TreeNode: arr list(map(int, data.split())) def construct(lower: int, upper: int) - TreeNode: if arr [] or arr[-1] lower or arr[-1] upper: return None val arr.pop() root TreeNode(val) root.right construct(val, upper) root.left construct(lower, val) return root return construct(-inf, inf)复杂度分析时间复杂度O(n) 其中 n 是树的节点数。serialize 需要 O(n) 时间遍历每个点。deserialize 需要 O(n) 时间恢复每个点。空间复杂度O(n) 其中 n 是树的节点数。serialize 需要 O(n) 空间用数组保存每个点的值递归的深度最深也为 O(n) 。deserialize 需要 O(n) 空间用数组保存每个点的值递归的深度最深也为 O(n) 。