297. 二叉树的序列化与反序列化（困难）

Blind 75 › 297. 二叉树的序列化与反序列化（困难） （第 11 章）
文章工具

题目

「序列化」把一棵二叉树变成字符串，方便存文件、传网络；「反序列化」再把这个字符串一对一地还原成最初那棵树。格式由你自定，唯一要求是：对任意合法 root，deserialize(serialize(root)) 重建出的树与原树等价。

因此字符串必须同时保留两类信息：节点值，以及树的形状（哪里是空、谁是谁的左子或右子）。

自造示例：树按层序写成 [4,2,null,1,3]——根是 4，左子是 2，2 的左、右分别是 1 和 3，根没有右子树。用本文约定可序列化为 "4,2,1,N,N,3,N,N,N"（N 表示空指针）。

约束：节点数 0 ~ 104；节点值 -1000 ~ 1000。判题页面常用层序数组展示输入输出（空节点写 null），但你的实现可以使用任意格式，最终只比较重建出来的树。

思路

一句话：选定一种遍历顺序，把“节点值”和“空指针”都当作 token 写进字符串；反序列化时按同一顺序，读一个 token 建一个节点。

最直白的做法是随手做一次前序遍历，把值拼起来。但只记值会丢失形状：[1,2]（左子是 2）和 [1,null,2]（右子是 2）前序都得到 1,2。字符串不唯一，自然无法唯一还原。

关键观察一：空指针也要写入。给两个例子补上空标记后，[1,2] → 1,2,N,N,N，[1,null,2] → 1,N,2,N,N，两者立刻可区分。空标记虽然“多写”，却把丢失的边界信息补了回来。

关键观察二：前序自带递归结构。记 S(空)="N"，S(节点)=val,S(左),S(右)。解码就是这条公式的反向执行：读一个 token，是 N 就返回空；是数字就建节点，再递归建左、右。左右边界由空标记自动划出，不用另存下标。

层序（LeetCode 展示格式）同样可行，但前序递归与“先建左再建右”的建树递归几乎逐行对应，代码最短。故本文选前序 DFS + 空标记 + 分隔符。

解法

序列化和反序列化像一对互逆动作，共用同一个“先左后右”的递归骨架：

  1. serialize：前序遍历；空节点写 N，非空写 val，token 之间加分隔符。
  2. deserialize：把字符串按分隔符切开，用一个“下一个待读”指针消费；读 N 返回空，读数字就建节点，再依次递归构造左、右。

用自造树 [4,2,null,1,3] 走一遍反序列化过程：

步读到动作剩余 token
14建根 4，先处理左子树2,1,N,N,3,N,N,N
22成为 4 的左子，先处理它的左子树1,N,N,3,N,N,N
31成为 2 的左子，接着补它两个空子N,N,3,N,N,N
4N1 的左子为空，转向 1 的右子N,3,N,N,N
5N1 的右子为空，返回去建 2 的右子树3,N,N,N
63成为 2 的右子，接着补它两个空子N,N,N
7~9N,N,N依次补 3 的左右空子、根 4 的右空子树空

C++ 用空格分隔，istringstream >> token 天然按空白切分；Python 用逗号分隔 + iter() 连读，避免 pop(0) 的 O(n) 开销。

下图把上面 2 个步骤串成流程，并逐步演示：

297. 二叉树的序列化与反序列化（困难） 解法步骤流程图
图① 解法步骤流程图（共 2 步）。
297. 二叉树的序列化与反序列化（困难） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Codec {
public:
    string serialize(TreeNode* root) {
        ostringstream out;
        encode(root, out);
        return out.str();
    }

    TreeNode* deserialize(string data) {
        istringstream in(data);
        return decode(in);
    }

private:
    void encode(TreeNode* root, ostringstream& out) {
        if (!root) {
            out << "N ";
            return;
        }
        out << root->val << ' ';
        encode(root->left, out);
        encode(root->right, out);
    }

    TreeNode* decode(istringstream& in) {
        string token;
        if (!(in >> token)) {
            return nullptr;      // 空串兜底
        }
        if (token == "N") {
            return nullptr;
        }
        TreeNode* node = new TreeNode(stoi(token));
        node->left = decode(in);
        node->right = decode(in);
        return node;
    }
};

Python

Python 3 示例