跳到主要内容

LeetCode 297. 二叉树的序列化与反序列化

本节目标

用包含空节点的前序协议保存值与结构，并按同一 token 顺序重建二叉树。

这是树上综合问题中的协议设计题：字符串不仅要保存节点值，还必须无歧义地保存树的左右结构。

查看 LeetCode 原题

题意与边界​

实现 Codec 的 serialize 与 deserialize。空树、负数和重复值都要正确处理；反序列化后再次序列化，必须得到同一份规范文本。

前序协议​

按前序输出节点值，用逗号分隔 token；空指针输出 #。例如单节点 1 编码为 1,#,#。若省略空节点，只有左孩子和只有右孩子的树可能写出同一串值，无法恢复结构。

反序列化顺序消费 token：读到 # 返回空；读到数值就新建节点，再依次递归构造左、右孩子。两个操作遵循同一前序规则，消费边界由空标记确定，不需要猜测子树长度。

正确性依据​

对树结构归纳。空树写入并读出 #，往返不变。非空根先写入自身值，再完整写入左、右子树的规范编码；解码时先恢复根，再按相同顺序消费恰好对应左右子树的 token。归纳假设保证两棵子树均被原样恢复，故整棵树的值与结构都一致。

代码实现​

C++17
class Codec {
public:
    std::string serialize(TreeNode* root) {
        std::string data;
        serializeDfs(root, data);
        data.pop_back();
        return data;
    }

    TreeNode* deserialize(std::string data) {
        std::vector<std::string> tokens;
        std::stringstream stream(data);
        std::string token;
        while (std::getline(stream, token, ',')) {
            tokens.push_back(token);
        }
        int index = 0;
        return deserializeDfs(tokens, index);
    }

private:
    void serializeDfs(TreeNode* node, std::string& data) {
        if (node == nullptr) {
            data += "#,";
            return;
        }

        data += std::to_string(node->val) + ',';
        serializeDfs(node->left, data);
        serializeDfs(node->right, data);
    }

    TreeNode* deserializeDfs(const std::vector<std::string>& tokens, int& index) {
        const std::string& token = tokens[index++];
        if (token == "#") {
            return nullptr;
        }

        TreeNode* node = new TreeNode(std::stoi(token));
        node->left = deserializeDfs(tokens, index);
        node->right = deserializeDfs(tokens, index);
        return node;
    }
};

复杂度分析​

序列化和反序列化都访问每个真实节点及其空孩子标记，时间复杂度为 O(n)。递归栈深度为 O(h)；输出文本或 token 容器占用 O(n) 空间。

边界与易错点​

  • 省略空节点，导致结构信息丢失。
  • 只保存层序值却不约定空位的表示方式。
  • deserialize 不按同一顺序消费 token，左右子树会错位。
  • 复用可变下标时没有在每次调用初始化，第二次解码会从错误位置开始。

模式迁移​

任何可逆编码都要先定义规范协议：数据字段、顺序、分隔方式和终止标记缺一不可。对象图存在共享引用或环时，则要额外编码节点标识，不能直接套用树的递归协议。