序列化和反序列化二叉搜索树 图解题解

这道题到底在问什么

输入

BST 根 50,左子树 30(20,40)、右子树 80(70,90)

输出

前序串 50,30,20,40,80,70,90

输入

空树

输出

空串

最优解：一步一步想明白

1. 3记住「序列化 = 前序、不存 null;反序列化 = 前序 + (lo, hi) 区间唯一定位」,下面分两段逐帧套它。
2. 4前序遍历先做序列化。规则是前序遍历:每到一个节点,先把它的值写进序列,再去左子树、最后去右子树。注意整个过程不写任何 null,这是 BST 比普通二叉树省空间的地方。
3. 5已写 1 个前序走到节点 50(紫色),把它的值写进序列,序列现在是 50。先记根,再去左子树。
4. 6已写 2 个前序走到节点 30(紫色),把它的值写进序列,序列现在是 50,30。接着按根、左、右的顺序继续。
5. 7已写 3 个前序走到节点 20(紫色),把它的值写进序列,序列现在是 50,30,20。接着按根、左、右的顺序继续。
6. 8已写 4 个前序走到节点 40(紫色),把它的值写进序列,序列现在是 50,30,20,40。接着按根、左、右的顺序继续。
7. 9已写 5 个前序走到节点 80(紫色),把它的值写进序列,序列现在是 50,30,20,40,80。接着按根、左、右的顺序继续。
8. 10已写 6 个前序走到节点 70(紫色),把它的值写进序列,序列现在是 50,30,20,40,80,70。接着按根、左、右的顺序继续。
9. 11已写 7 个前序走到节点 90(紫色),把它的值写进序列,序列现在是 50,30,20,40,80,70,90。这是最后一个节点。
10. 12得到前序串序列化完成,得到前序串 50,30,20,40,80,70,90,一共 7 个值、没有一个 null。接下来反过来,只凭这串数把整棵 BST 还原出来。
11. 13读前序串开始反序列化。手里只有前序串 50,30,20,40,80,70,90。我们从左往右取值,每个位置都带一个允许区间 (lo, hi):根节点的区间是 (-∞, +∞),最宽松。
12. 14读到第 1 个根:取到值 50,它满足 -∞ < 50 < +∞,于是在这里建节点 50。接着它的左子树区间收紧为 (-∞, 50)、右子树区间为 (50, +∞),继续往下递归。
13. 15读到第 2 个节点 50 的左孩子:取到值 30,它满足 -∞ < 30 < 50,于是在这里建节点 30。接着它的左子树区间收紧为 (-∞, 30)、右子树区间为 (30, 50),继续往下递归。
14. 16读到第 3 个节点 30 的左孩子:取到值 20,它满足 -∞ < 20 < 30,于是在这里建节点 20。接着它的左子树区间收紧为 (-∞, 20)、右子树区间为 (20, 30),继续往下递归。
15. 17区间不符轮到节点 20 的左孩子,它的允许区间是 (-∞, 20)。但下一个待读的值 40 不落在区间里,说明这里没有节点,直接判为空,既不取值也不前进,回到上一层。
16. 18区间不符轮到节点 20 的右孩子,它的允许区间是 (20, 30)。但下一个待读的值 40 不落在区间里,说明这里没有节点,直接判为空,既不取值也不前进,回到上一层。
17. 19读到第 4 个节点 30 的右孩子:取到值 40,它满足 30 < 40 < 50,于是在这里建节点 40。接着它的左子树区间收紧为 (30, 40)、右子树区间为 (40, 50),继续往下递归。
18. 20读到第 5 个节点 50 的右孩子:取到值 80,它满足 50 < 80 < +∞,于是在这里建节点 80。接着它的左子树区间收紧为 (50, 80)、右子树区间为 (80, +∞),继续往下递归。
19. 21读到第 6 个节点 80 的左孩子:取到值 70,它满足 50 < 70 < 80,于是在这里建节点 70。接着它的左子树区间收紧为 (50, 70)、右子树区间为 (70, 80),继续往下递归。
20. 22读到第 7 个节点 80 的右孩子:取到值 90,它满足 80 < 90 < +∞,于是在这里建节点 90。接着它的左子树区间收紧为 (80, 90)、右子树区间为 (90, +∞),继续往下递归。
21. 23原样还原整串读完,还原出的 BST 和原来完全一样。验证一下它的中序是 20,30,40,50,70,80,90,严格升序,确实是合法 BST。这正是 BST 的妙处:前序串配上 (lo,hi) 区间,每个值的位置都被唯一确定。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import Optional
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        vals = []
        def dfs(node):
            if node:
                vals.append(str(node.val))
                dfs(node.left)
                dfs(node.right)
        dfs(root)
        return ','.join(vals)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        if not data:
            return None
        vals = list(map(int, data.split(',')))
        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'))

#include <sstream>
#include <string>
#include <vector>
using namespace std;
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x): val(x), left(nullptr), right(nullptr) {} };
class Codec {
public:
    string serialize(TreeNode* root) {
        vector<string> vals;
        function<void(TreeNode*)> dfs = [&](TreeNode* n){ if(!n) return; vals.push_back(to_string(n->val)); dfs(n->left); dfs(n->right); };
        dfs(root);
        string out;
        for (int i = 0; i < (int)vals.size(); ++i) { if (i) out += ","; out += vals[i]; }
        return out;
    }
    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;
        vector<int> vals; string token; stringstream ss(data);
        while (getline(ss, token, ',')) vals.push_back(stoi(token));
        int i = 0;
        function<TreeNode*(long long,long long)> build = [&](long long lo, long long hi) {
            if (i == (int)vals.size() || vals[i] <= lo || vals[i] >= hi) return (TreeNode*)nullptr;
            TreeNode* n = new TreeNode(vals[i++]);
            n->left = build(lo, n->val);
            n->right = build(n->val, hi);
            return n;
        };
        return build(LLONG_MIN, LLONG_MAX);
    }
};

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        preorder(root, sb);
        return sb.toString();
    }
    private void preorder(TreeNode node, StringBuilder sb) {
        if (node == null) return;
        if (sb.length() > 0) sb.append(',');
        sb.append(node.val);
        preorder(node.left, sb);
        preorder(node.right, sb);
    }
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        String[] parts = data.split(",");
        int[] vals = new int[parts.length];
        for (int i = 0; i < parts.length; i++) vals[i] = Integer.parseInt(parts[i]);
        int[] idx = {0};
        return build(vals, idx, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private TreeNode build(int[] vals, int[] idx, long lo, long hi) {
        if (idx[0] == vals.length || vals[idx[0]] <= lo || vals[idx[0]] >= hi) return null;
        TreeNode node = new TreeNode(vals[idx[0]++]);
        node.left = build(vals, idx, lo, node.val);
        node.right = build(vals, idx, node.val, hi);
        return node;
    }
}

复杂度

面试官可能追问