LeetCode 题解工作台
序列化和反序列化二叉搜索树
序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。 设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串…
7
题型
4
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
题目给定的是二叉搜索树，我们知道二叉搜索树的中序遍历是有序的，而通过“先序遍历”和“中序遍历”可以唯一确定一棵二叉树，所以我们可以通过先序遍历的结果和中序遍历的结果来唯一确定一棵二叉搜索树。 在 `serialize` 方法中，我们使用先序遍历的方式将二叉搜索树序列化为空格分隔的字符串，然后在 `deserialize` 方法中，我们将字符串按空格分割为数组，然后使用递归的方式来构建二叉搜索树。递…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
示例 1：
输入：root = [2,1,3] 输出：[2,1,3]
示例 2：
输入：root = [] 输出：[]
提示：
- 树中节点数范围是
[0, 104] 0 <= Node.val <= 104- 题目数据 保证 输入的树是一棵二叉搜索树。
解题思路
方法一：先序遍历
题目给定的是二叉搜索树，我们知道二叉搜索树的中序遍历是有序的，而通过“先序遍历”和“中序遍历”可以唯一确定一棵二叉树，所以我们可以通过先序遍历的结果和中序遍历的结果来唯一确定一棵二叉搜索树。
在 serialize 方法中，我们使用先序遍历的方式将二叉搜索树序列化为空格分隔的字符串，然后在 deserialize 方法中，我们将字符串按空格分割为数组，然后使用递归的方式来构建二叉搜索树。递归函数为 ，表示当前节点的值必须在 之间，如果当前节点的值不在 之间，则说明这个节点不是当前递归树的节点，返回 None。
时间复杂度 ，空间复杂度 。其中 是二叉搜索树的节点数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root: Optional[TreeNode]) -> str:
"""Encodes a tree to a single string."""
def dfs(root: Optional[TreeNode]):
if root is None:
return
nums.append(root.val)
dfs(root.left)
dfs(root.right)
nums = []
dfs(root)
return " ".join(map(str, nums))
def deserialize(self, data: str) -> Optional[TreeNode]:
"""Decodes your encoded data to tree."""
def dfs(mi: int, mx: int) -> Optional[TreeNode]:
nonlocal i
if i == len(nums) or not mi <= nums[i] <= mx:
return None
x = nums[i]
root = TreeNode(x)
i += 1
root.left = dfs(mi, x)
root.right = dfs(x, mx)
return root
nums = list(map(int, data.split()))
i = 0
return dfs(-inf, inf)
# Your Codec object will be instantiated and called as such:
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's understanding of tree traversal methods and how they relate to serialization.
- question_mark
Evaluate the ability to choose the most space-efficient approach based on the tree's size and structure.
- question_mark
Assess the candidate's attention to detail in handling edge cases, such as empty trees or trees with a large number of nodes.
常见陷阱
外企场景- error
Over-complicating the algorithm by not considering simple traversal techniques like pre-order or BFS.
- error
Failing to account for null nodes during serialization, leading to incorrect deserialization.
- error
Not optimizing for space in scenarios with large trees, resulting in excessive memory usage.
进阶变体
外企场景- arrow_right_alt
Using a post-order or in-order traversal for serialization instead of pre-order.
- arrow_right_alt
Implementing the solution iteratively without recursion.
- arrow_right_alt
Optimizing the solution for trees with high depth and low width.