449. 序列化和反序列化二叉搜索树
题目描述
设计一个 Codec 类，负责二叉搜索树与字符串之间的相互转换。
serialize(root)：把以 root 为根的二叉搜索树编码为一个字符串并返回。deserialize(data)：把 serialize 得到的字符串还原成树，返回根节点。
编码格式由你自己决定，只要还原后的树和原树完全一致即可。编码结果应当尽量短。
测试时会先编码、再解码，比较得到的树。树用层序数组表示，空树为 []。
示例 1
输入：root = [2,1,3] 输出：[2,1,3]
解释：编码再解码后得到与原树相同的 [2,1,3]。
示例 2
输入：root = [] 输出：[]
解释：空树编码后还原仍是空树。
数据范围
- 节点个数在
[0, 10^4]范围内。 0 <= Node.val <= 10^4- 输入一定是一棵二叉搜索树。
解题思路：先序遍历 + 上下界递归重建
二叉搜索树的前序序列已经能唯一确定这棵树，所以不需要空位记号，只写出节点值即可。反序列化时，给每次 build 调用一个开区间 (lo, hi)：如果下一个值落在区间内，它就是这棵子树的根，消费它后用 (lo, 根) 建左子树、用 (根, hi) 建右子树；否则这棵子树为空，值留给祖先的右子树。
为什么正确
build(lo, hi) 被调用时，vals[i] 之前的值都已挂到树上；这棵子树恰好由从 i 开始、连续落在 (lo, hi) 内的那一段前序值组成。
复杂度分析
时间 O(n)，每个值只被消费一次；空间 O(n)，递归深度为树高。
易错点
区间必须是开区间，并且向下传递时要同时收紧上下界。只比较父节点大小会把值挂错位置。另外空树序列化为空字符串，反序列化时要先过滤掉空串，不能把它当数字解析。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Codec:
def serialize(self, root):
out = []
def dfs(node):
if not node:
return
out.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ','.join(out)
def deserialize(self, data):
vals = [int(x) for x in data.split(',') if x]
i = 0
def build(lo, hi):
nonlocal i
if i == len(vals) or not (lo < vals[i] < hi):
return None
node = TreeNode(vals[i])
i += 1
node.left = build(lo, node.val)
node.right = build(node.val, hi)
return node
return build(float('-inf'), float('inf'))class Codec {
public String serialize(TreeNode root) {
StringBuilder out = new StringBuilder();
dfs(root, out);
return out.toString();
}
private void dfs(TreeNode node, StringBuilder out) {
if (node == null) {
return;
}
if (out.length() > 0) {
out.append(',');
}
out.append(node.val);
dfs(node.left, out);
dfs(node.right, out);
}
private int[] vals;
private int i;
public TreeNode deserialize(String data) {
vals = data.isEmpty() ? new int[0] : Arrays.stream(data.split(",")).mapToInt(Integer::parseInt).toArray();
i = 0;
return build(Long.MIN_VALUE, Long.MAX_VALUE);
}
private TreeNode build(long lo, long hi) {
if (i == vals.length || !(lo < vals[i] && vals[i] < hi)) {
return null;
}
TreeNode node = new TreeNode(vals[i]);
i++;
node.left = build(lo, node.val);
node.right = build(node.val, hi);
return node;
}
}class Codec {
public:
string serialize(TreeNode* root) {
string out;
dfs(root, out);
return out;
}
void dfs(TreeNode* node, string& out) {
if (!node) {
return;
}
if (!out.empty()) {
out += ',';
}
out += to_string(node->val);
dfs(node->left, out);
dfs(node->right, out);
}
TreeNode* deserialize(string data) {
vector<int> vals;
stringstream ss(data);
string tok;
while (getline(ss, tok, ',')) {
if (!tok.empty()) {
vals.push_back(stoi(tok));
}
}
int i = 0;
return build(vals, i, LLONG_MIN, LLONG_MAX);
}
TreeNode* build(const vector<int>& vals, int& i, long long lo, long long hi) {
if (i == (int)vals.size() || !(lo < vals[i] && vals[i] < hi)) {
return nullptr;
}
TreeNode* node = new TreeNode(vals[i]);
i++;
node->left = build(vals, i, lo, node->val);
node->right = build(vals, i, node->val, hi);
return node;
}
};type Codec struct {
}
func Constructor() Codec {
return Codec{}
}
func (this *Codec) serialize(root *TreeNode) string {
out := []string{}
var dfs func(node *TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
out = append(out, strconv.Itoa(node.Val))
dfs(node.Left)
dfs(node.Right)
}
dfs(root)
return strings.Join(out, ",")
}
func (this *Codec) deserialize(data string) *TreeNode {
vals := []int{}
for _, s := range strings.Split(data, ",") {
if s != "" {
x, _ := strconv.Atoi(s)
vals = append(vals, x)
}
}
i := 0
var build func(lo, hi int) *TreeNode
build = func(lo, hi int) *TreeNode {
if i == len(vals) || !(lo < vals[i] && vals[i] < hi) {
return nil
}
node := &TreeNode{Val: vals[i]}
i++
node.Left = build(lo, node.Val)
node.Right = build(node.Val, hi)
return node
}
return build(math.MinInt64, math.MaxInt64)
}var serialize = function(root) {
const out = [];
const dfs = (node) => {
if (!node) {
return;
}
out.push(String(node.val));
dfs(node.left);
dfs(node.right);
};
dfs(root);
return out.join(',');
};
var deserialize = function(data) {
const vals = data ? data.split(',').map(Number) : [];
let i = 0;
const build = (lo, hi) => {
if (i === vals.length || !(lo < vals[i] && vals[i] < hi)) {
return null;
}
const node = new TreeNode(vals[i]);
i++;
node.left = build(lo, node.val);
node.right = build(node.val, hi);
return node;
};
return build(-Infinity, Infinity);
};function serialize(root: TreeNode | null): string {
const out: string[] = [];
const dfs = (node: TreeNode | null): void => {
if (!node) {
return;
}
out.push(String(node.val));
dfs(node.left);
dfs(node.right);
};
dfs(root);
return out.join(',');
}
function deserialize(data: string): TreeNode | null {
const vals: number[] = data ? data.split(',').map(Number) : [];
let i = 0;
const build = (lo: number, hi: number): TreeNode | null => {
if (i === vals.length || !(lo < vals[i] && vals[i] < hi)) {
return null;
}
const node = new TreeNode(vals[i]);
i++;
node.left = build(lo, node.val);
node.right = build(node.val, hi);
return node;
};
return build(-Infinity, Infinity);
}其他解法
上下界递归直接用 BST 性质划分区间，代码短；单调栈是迭代写法，避免深递归。
解法 2：先序遍历 + 单调栈重建 时间 O(n)，空间 O(n)
序列化仍输出先序序列，用显式栈遍历。反序列化时维护一个从底到顶值递减的栈：新值小于栈顶就作为栈顶的左孩子；否则不断弹出比它小的节点，最后弹出的那个就是它的父节点，新值作为父节点的右孩子。每个新节点都要入栈。
全程不递归，树退化成链时也不会栈溢出。需要理解单调栈为什么能找到父节点，不如上下界递归直观。
class Codec:
def serialize(self, root):
# 用显式栈做先序遍历
out = []
stack = [root] if root else []
while stack:
node = stack.pop()
out.append(str(node.val))
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return ','.join(out)
def deserialize(self, data):
vals = [int(x) for x in data.split(',') if x]
if not vals:
return None
root = TreeNode(vals[0])
stack = [root] # 栈中节点值从底到顶递减
for v in vals[1:]:
node = TreeNode(v)
if v < stack[-1].val:
stack[-1].left = node
else:
parent = None
while stack and stack[-1].val < v:
parent = stack.pop()
parent.right = node
stack.append(node)
return rootclass Codec {
public String serialize(TreeNode root) {
StringBuilder out = new StringBuilder();
Deque<TreeNode> st = new ArrayDeque<>();
if (root != null) st.push(root);
while (!st.isEmpty()) {
TreeNode node = st.pop();
if (out.length() > 0) out.append(',');
out.append(node.val);
if (node.right != null) st.push(node.right);
if (node.left != null) st.push(node.left);
}
return out.toString();
}
public TreeNode deserialize(String data) {
if (data.isEmpty()) return null;
int[] vals = Arrays.stream(data.split(",")).mapToInt(Integer::parseInt).toArray();
TreeNode root = new TreeNode(vals[0]);
Deque<TreeNode> st = new ArrayDeque<>();
st.push(root);
for (int i = 1; i < vals.length; i++) {
TreeNode node = new TreeNode(vals[i]);
if (vals[i] < st.peek().val) {
st.peek().left = node;
} else {
TreeNode parent = null;
while (!st.isEmpty() && st.peek().val < vals[i]) parent = st.pop();
parent.right = node;
}
st.push(node);
}
return root;
}
}class Codec {
public:
string serialize(TreeNode* root) {
string out;
vector<TreeNode*> st;
if (root) st.push_back(root);
while (!st.empty()) {
TreeNode* node = st.back();
st.pop_back();
if (!out.empty()) out += ',';
out += to_string(node->val);
if (node->right) st.push_back(node->right);
if (node->left) st.push_back(node->left);
}
return out;
}
TreeNode* deserialize(string data) {
vector<int> vals;
stringstream ss(data);
string tok;
while (getline(ss, tok, ',')) {
if (!tok.empty()) vals.push_back(stoi(tok));
}
if (vals.empty()) return nullptr;
TreeNode* root = new TreeNode(vals[0]);
vector<TreeNode*> st = {root};
for (int i = 1; i < (int)vals.size(); i++) {
TreeNode* node = new TreeNode(vals[i]);
if (vals[i] < st.back()->val) {
st.back()->left = node;
} else {
TreeNode* parent = nullptr;
while (!st.empty() && st.back()->val < vals[i]) {
parent = st.back();
st.pop_back();
}
parent->right = node;
}
st.push_back(node);
}
return root;
}
};type Codec struct {
}
func Constructor() Codec {
return Codec{}
}
func (this *Codec) serialize(root *TreeNode) string {
out := []string{}
st := []*TreeNode{}
if root != nil {
st = append(st, root)
}
for len(st) > 0 {
node := st[len(st)-1]
st = st[:len(st)-1]
out = append(out, strconv.Itoa(node.Val))
if node.Right != nil {
st = append(st, node.Right)
}
if node.Left != nil {
st = append(st, node.Left)
}
}
return strings.Join(out, ",")
}
func (this *Codec) deserialize(data string) *TreeNode {
vals := []int{}
for _, s := range strings.Split(data, ",") {
if s != "" {
x, _ := strconv.Atoi(s)
vals = append(vals, x)
}
}
if len(vals) == 0 {
return nil
}
root := &TreeNode{Val: vals[0]}
st := []*TreeNode{root}
for _, v := range vals[1:] {
node := &TreeNode{Val: v}
if v < st[len(st)-1].Val {
st[len(st)-1].Left = node
} else {
var parent *TreeNode
for len(st) > 0 && st[len(st)-1].Val < v {
parent = st[len(st)-1]
st = st[:len(st)-1]
}
parent.Right = node
}
st = append(st, node)
}
return root
}var serialize = function(root) {
const out = [];
const st = root ? [root] : [];
while (st.length) {
const node = st.pop();
out.push(String(node.val));
if (node.right) st.push(node.right);
if (node.left) st.push(node.left);
}
return out.join(',');
};
var deserialize = function(data) {
const vals = data.split(',').filter(x => x !== '').map(Number);
if (!vals.length) return null;
const root = new TreeNode(vals[0]);
const st = [root];
for (let i = 1; i < vals.length; i++) {
const node = new TreeNode(vals[i]);
if (vals[i] < st[st.length - 1].val) {
st[st.length - 1].left = node;
} else {
let parent = null;
while (st.length && st[st.length - 1].val < vals[i]) parent = st.pop();
parent.right = node;
}
st.push(node);
}
return root;
};function serialize(root: TreeNode | null): string {
const out: string[] = [];
const st: TreeNode[] = root ? [root] : [];
while (st.length) {
const node = st.pop()!;
out.push(String(node.val));
if (node.right) st.push(node.right);
if (node.left) st.push(node.left);
}
return out.join(',');
}
function deserialize(data: string): TreeNode | null {
const vals = data.split(',').filter(x => x !== '').map(Number);
if (!vals.length) return null;
const root = new TreeNode(vals[0]);
const st: TreeNode[] = [root];
for (let i = 1; i < vals.length; i++) {
const node = new TreeNode(vals[i]);
if (vals[i] < st[st.length - 1].val) {
st[st.length - 1].left = node;
} else {
let parent: TreeNode | null = null;
while (st.length && st[st.length - 1].val < vals[i]) parent = st.pop()!;
parent!.right = node;
}
st.push(node);
}
return root;
}