二叉树的序列化与反序列化 图解题解

这道题真正要设计的是什么

题目要求写一对互逆的函数：serialize 把任意二叉树编码成一个字符串，deserialize 再把这个字符串还原成一模一样的树，deserialize(serialize(root)) 必须等于原树。难点不在遍历本身，而在于字符串必须携带足够的信息——不但要记录每个节点的值，还要能还原树的形状。同样一串值 1,2,3，既可能是一条斜向一边的链，也可能是一棵根带两个孩子的树，只记值是不够的。

为什么必须给空孩子写 # 占位符

形状信息丢失的根源在于：普通遍历序列把空位置跳过了，读串的人分不清「下一个值是当前节点的孩子，还是拐回上层挂在别处」。补救办法是把空也当成一个字符写出来：先序遍历时每碰到一个空孩子就写一个 #。这样每个节点名下左、右两个孩子位置都有明确交代，值序列和树的形状就一一对应了。

代价是串变长：n 个节点会带出 n+1 个 #（共 2n 个孩子位置，其中 n-1 个被真实节点占据）。多出的这点长度换来的是零歧义，这是序列化方案里常见的交易。

为什么选先序遍历而不是中序或层序

先序的好处是根永远排在串的最前面：反序列化取出第一个 token 就能立刻建出根；按「根、左、右」的定义，紧随其后的一段恰好是完整的左子树，再往后是完整的右子树，天然适合递归重建。中序把根夹在左右子树中间，拿到串时不知道该从哪里切开，难以定位根。层序配合占位符同样可行（用队列逐层重建），但先序递归的代码最短，还和序列化共用同一套遍历骨架。真正的铁律只有一条：序列化和反序列化必须用同一种顺序，顺序一旦错位，孩子就会挂错位置、整棵树扭曲。

反序列化为什么取一个 token 就能精确归位

把字符串按逗号切成 token 队列后，重建函数的逻辑是：从队头取一个 token，是 # 就返回空，否则建节点、先递归建左子树、再递归建右子树。正确性来自先序串的结构不变量：任何一棵子树在串里都是连续的一段，且这段的开头就是该子树的根。递归建左子树时会恰好消费掉左子树对应的那段 token，返回时队头自动停在右子树的开头——不需要任何额外的分隔符或长度标记。

一个隐蔽的坑：# 也必须从队列里消费掉。它虽然不建节点，但占着一个位置，不弹出的话后续 token 全部错位，还原出来的树会整体歪掉。

复杂度是多少，哪里容易翻车

序列化和反序列化都是每个 token 恰好处理一次，时间各为 O(n)。空间 O(n)：字符串本身是线性长度，递归栈深等于树高 h，最坏退化成链时也是 O(n)。

两个高频错误：一是不写空占位符，看似省了空间，实则丢了形状信息，根本还原不出唯一的树；二是两边遍历顺序不一致，比如序列化用先序、反序列化却按别的顺序读，token 数量对得上但结构全错。

Java

public class Codec {
    // 序列化：先序遍历，空节点写 "#"，逗号分隔
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        dfsSer(root, sb);
        return sb.toString();
    }
    private void dfsSer(TreeNode node, StringBuilder sb) {
        if (node == null) { sb.append("#,"); return; }   // 空 → # 占位
        sb.append(node.val).append(",");                 // 根先写
        dfsSer(node.left, sb);                            // 再左
        dfsSer(node.right, sb);                           // 后右
    }
    // 反序列化：按逗号切成队列，先序逐个重建
    public TreeNode deserialize(String data) {
        Deque<String> q = new ArrayDeque<>(Arrays.asList(data.split(",")));
        return build(q);
    }
    private TreeNode build(Deque<String> q) {
        String t = q.poll();                              // 取队头
        if (t.equals("#")) return null;                   // # → 空
        TreeNode node = new TreeNode(Integer.parseInt(t));
        node.left  = build(q);                            // 先建左
        node.right = build(q);                            // 再建右
        return node;
    }
}

Python

class Codec:
    def serialize(self, root):
        out = []
        def dfs(node):
            if node is None:
                out.append("#")          # 空 → # 占位
                return
            out.append(str(node.val))    # 根先写
            dfs(node.left)               # 再左
            dfs(node.right)              # 后右
        dfs(root)
        return ",".join(out)

    def deserialize(self, data):
        vals = iter(data.split(","))     # token 队列
        def build():
            t = next(vals)               # 取队头
            if t == "#":
                return None              # # → 空
            node = TreeNode(int(t))
            node.left = build()          # 先建左
            node.right = build()         # 再建右
            return node
        return build()

C++

class Codec {
public:
    string serialize(TreeNode* root) {
        string s;
        function<void(TreeNode*)> dfs = [&](TreeNode* n){
            if (!n) { s += "#,"; return; }          // 空 → # 占位
            s += to_string(n->val) + ",";           // 根先写
            dfs(n->left);                            // 再左
            dfs(n->right);                           // 后右
        };
        dfs(root);
        return s;
    }
    TreeNode* deserialize(string data) {
        stringstream ss(data); string t;
        queue<string> q;
        while (getline(ss, t, ',')) if (!t.empty()) q.push(t);
        function<TreeNode*()> build = [&]() -> TreeNode* {
            string x = q.front(); q.pop();           // 取队头
            if (x == "#") return nullptr;            // # → 空
            TreeNode* n = new TreeNode(stoi(x));
            n->left  = build();                      // 先建左
            n->right = build();                      // 再建右
            return n;
        };
        return build();
    }
};