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

🟠   🔖  树 深度优先搜索 广度优先搜索 设计 二叉搜索树 字符串 二叉树  🔗 力扣 LeetCode

题目

Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Example 1:

Input: root = [2,1,3]

Output: [2,1,3]

Example 2:

Input: root = []

Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• 0 <= Node.val <= 10^4
• The input tree is guaranteed to be a binary search tree.

题目大意

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

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

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

示例 1：

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

输出：[2,1,3]

示例 2：

输入： root = []

输出：[]

提示：

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

解题思路

本题要求对 二叉搜索树（BST） 进行 序列化（转字符串）和 反序列化（恢复原树）。
由于 BST 的前序遍历（Preorder）可以唯一确定 BST 结构，我们可以利用这一性质高效完成题目。

1. 序列化（Serialize）

• 采用 前序遍历（先根后左右） 遍历 BST，并 将节点值存入数组。
• 遇到 null 不存储，只存非空节点的值，减少存储开销。

复杂度分析

• 时间复杂度： O(n)，遍历所有 n 个节点一次。
• 空间复杂度： O(n)，存储 n 个节点的值。

---

2. 反序列化（Deserialize）

• 由于 preorder 遍历是 根 → 左 → 右：
  1. 取出当前子树的根节点（数组第一个元素）。
  2. 利用 BST 的性质（左子树 < 根 < 右子树），用上下界 lower 和 upper 限制节点值范围：
     • 左子树 递归构造范围 [lower, root.val]。
     • 右子树 递归构造范围 [root.val, upper]。
  3. 如果当前值不在 [lower, upper] 范围内，说明不属于当前子树，回溯。

复杂度分析

• 时间复杂度： O(n)，每个节点最多访问一次。
• 空间复杂度： O(n)，递归栈的最大深度 最坏 O(n)（退化为链表），最优 O(log n)（平衡 BST）。

代码

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
	let arr = [];

	const preorder = (node) => {
		if (!node) return;
		arr.push(node.val);
		preorder(node.left);
		preorder(node.right);
	};

	preorder(root);
	return arr.join(',');
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
	if (!data) return null;

	const arr = data.split(',').map(Number);

	const buildTree = (lower, upper) => {
		if (!arr.length || arr[0] < lower || arr[0] > upper) return null;

		let val = arr.shift();
		let root = new TreeNode(val);
		root.left = buildTree(lower, val);
		root.right = buildTree(val, upper);
		return root;
	};

	return buildTree(-Infinity, Infinity);
};

相关题目

题号	标题	题解	标签	难度	力扣
297	二叉树的序列化与反序列化	[✓]	树 深度优先搜索 广度优先搜索 3+	🔴	🀄️ 🔗
428	序列化和反序列化 N 叉树 🔒		树 深度优先搜索 广度优先搜索 1+	🔴	🀄️ 🔗
652	寻找重复的子树		树 深度优先搜索 哈希表 1+	🟠	🀄️ 🔗