面试题37：序列化二叉树

以前序顺序写出节点值与美元符号空位，并让反序列化游标按同一递归结构逐记号消费，恢复唯一树形。

学习目标

  • 能用前序写出节点值与空位占位符序列化二叉树
  • 能解释空节点占位符消除结构歧义
  • 能让反序列化游标按同一递归结构恢复树形

从“两个5为什么不能说明谁是左孩子”开始

先预测：根5只有左孩子5，与根5只有右孩子5，如果只写前序值都得到5、5。没有空位置，就无法知道第二个5在哪一侧，反序列化也不可能唯一选择。

作者“序列化二叉树”采用。非空节点写十进制整数和逗号；空节点写美元符号加逗号。旧页使用#是常见变体，但不是作者格式。

前序：节点 → 左子树 → 右子树；空位置也占一个token861057911806152$3$475$6$710899$10$111112$13$148,6,5,$,$,7,$,$,10,9,$,$,11,$,$,
n个真实节点的完整前序空位编码含n+1个$标记，共2n+1个token。

例如完整三层树得到8,6,5,$,$,7,$,$,10,9,$,$,11,$,$,。尾部逗号属于作者输出，每个token都由逗号终止。

空节点为何消除结构歧义

$不携带节点值，却保存树形边界。遇到数字说明有节点并必须继续读取左右两棵子树；遇到$说明当前分支立即结束。

树形省略空位作者编码结论
根5的左孩子5只看值前序：5,55,5,$,$,$,左结构
根5的右孩子5只看值前序：5,55,$,5,$,$,右结构
单节点5只看值前序：55,$,$,两个空孩子
空树无值$,一个空根token
Test6全值5值序列无法区分$位置唯一恢复不规则形状可逆
相同值前序可对应不同拓扑；显式空节点占位符使编码与树结构一一对应。

对n个真实节点，二叉树共有n减1条真实父子边；2n个孩子槽位中，空槽数量是2n减n减1，也就是n+1。因此完整编码有n个数字token和n+1个$ token，共2n+1个。这也提供基本长度校验。

Test6所有9个节点值都为5，仅看值完全无法区分形状；$分布仍能恢复每个左右空位。序列化不是压缩值，而是编码值与拓扑。

忠实还原作者

Serialize递归写ostream。空节点写"$,"后返回；非空先写值和逗号，再写左右子树。

#include <cstdlib>
#include <istream>
#include <ostream>
 
struct BinaryTreeNode {
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};
 
void Serialize(const BinaryTreeNode* pRoot,
               std::ostream& stream) {
    if (pRoot == nullptr) {
        stream << "$,";
        return;
    }
 
    stream << pRoot->m_nValue << ',';
    Serialize(pRoot->m_pLeft, stream);
    Serialize(pRoot->m_pRight, stream);
}
 
bool ReadStream(std::istream& stream, int* number) {
    if (stream.eof()) return false;
 
    char buffer[32];
    buffer[0] = '\0';
    char ch;
    stream >> ch;
    int i = 0;
    while (!stream.eof() && ch != ',') {
        buffer[i++] = ch;
        stream >> ch;
    }
 
    bool isNumeric = false;
    if (i > 0 && buffer[0] != '$') {
        *number = std::atoi(buffer);
        isNumeric = true;
    }
    return isNumeric;
}
 
void Deserialize(BinaryTreeNode** pRoot,
                 std::istream& stream) {
    int number;
    if (ReadStream(stream, &number)) {
        *pRoot = new BinaryTreeNode{
            number, nullptr, nullptr};
        Deserialize(&((*pRoot)->m_pLeft), stream);
        Deserialize(&((*pRoot)->m_pRight), stream);
    }
}

作者ReadStream把“读到数字”返回true，把$或EOF返回false。Deserialize只有数字时分配节点，孩子在递归前先设null；因此$分支无需额外写指针。

当前token动作递归语义下个索引
读8创建根8接下来构造8.left1
读6创建节点6接下来构造6.left2
读5创建叶候选5继续读取两个孩子3
读$5.left=null不再递归该分支4
读$5.right=null返回节点55
后续依次完成6.right与8.right每个递归恰消费一棵子树直到15
反序列化游标单调前进；数字消费自身及左右子树，$只消费一个空分支。

这套代码用于可信示例文件。32字节buffer没有边界检查，超长token会写越界；atoi不报告非法字符或范围溢出；截断输入可能被当作空分支；函数也不拒绝完整树后的多余token。生产解析必须显式返回成功或失败。

严格的格式契约

把逗号分割后的字符串称为。严格解析应拒绝空token、非法整数、数值越界、提前结束和根树之后的尾随token；构造失败时释放已分配前缀。

下面用unique_ptr保证失败自动清理，并用from_chars做无区域设置、可检查的整数转换。它接受作者的尾随逗号，但不要求调用方通过文件流：

#include <charconv>
#include <memory>
#include <string>
#include <string_view>
#include <system_error>
#include <vector>
 
struct TreeNode {
    int value;
    std::unique_ptr<TreeNode> left;
    std::unique_ptr<TreeNode> right;
};
 
class StrictCodec {
public:
    bool deserialize(
        std::string_view data,
        std::unique_ptr<TreeNode>& output) {
        tokens_.clear();
        index_ = 0;
 
        std::size_t begin = 0;
        while (begin < data.size()) {
            const std::size_t comma = data.find(',', begin);
            const std::size_t end =
                comma == std::string_view::npos
                    ? data.size() : comma;
            if (end == begin) return false;
            tokens_.push_back(data.substr(begin, end - begin));
            if (comma == std::string_view::npos) break;
            begin = comma + 1;
        }
 
        std::unique_ptr<TreeNode> candidate;
        if (!parse(candidate) || index_ != tokens_.size()) {
            return false;
        }
        output = std::move(candidate);
        return true;
    }
 
private:
    bool parse(std::unique_ptr<TreeNode>& output) {
        if (index_ >= tokens_.size()) return false;
        const std::string_view token = tokens_[index_++];
        if (token == "$") {
            output.reset();
            return true;
        }
 
        int value = 0;
        const auto [ptr, error] = std::from_chars(
            token.data(), token.data() + token.size(), value);
        if (error != std::errc{} ||
            ptr != token.data() + token.size()) {
            return false;
        }
 
        auto node = std::make_unique<TreeNode>();
        node->value = value;
        if (!parse(node->left) || !parse(node->right)) {
            return false;
        }
        output = std::move(node);
        return true;
    }
 
    std::vector<std::string_view> tokens_;
    std::size_t index_ = 0;
};

输入空字符串没有token，返回false；"$,"解析为合法空树。最后的index检查拒绝"$,$,"这类树后多余数据。若格式规定必须尾随逗号，还可额外检查data.back；这里兼容有无最后逗号，但序列化仍输出作者格式。

把格式版本、字符编码、整数范围、最大节点数和最大深度写入。否则同一字符串在不同实现中可能得到不同结果。

为何能唯一恢复

维护一个单调前进的。读到$返回空；读到数字创建根，然后递归消费左子树，再消费右子树。

前序让根先出现，$又明确每个空分支，递归无需回看或猜测子树长度。一个数字token启动两个子解析，一个$结束一个子解析；完整树恰好平衡所有待填孩子槽位。

若输入提前结束，仍有待填槽位，严格解析失败；若根完成后仍有token，说明输入包含第二棵树或垃圾，也失败。这是比“尽量构造”更适合持久化和网络协议的策略。

作者六组往返测试

Test1是8、6、10与5、7、9、11组成的完整三层树。Test2全左链5、4、3、2，Test3全右链5、4、3、2；两者验证$在每层不同方向的位置。Test4单节点5编码为5,$,$,，Test5空树编码为$,。

Test6有9个值全为5的节点，左右结构不规则，专门验证空位而不是数值决定拓扑。每组都写入test.txt，再读回新树，并用isSameTree递归比较结构和值。源码总计六组。

作者打印文件使用while(!eof())再提取字符，这是经典流读取反模式：最后一次提取失败后仍可能输出旧ch。正确打印应写while(fileIn >> ch)。这不影响Deserialize读取另一条新ifstream，但测试展示可能多一个末字符。

#include <cassert>
#include <memory>
 
bool sameTree(const TreeNode* a, const TreeNode* b) {
    if (a == nullptr || b == nullptr) return a == b;
    return a->value == b->value &&
           sameTree(a->left.get(), b->left.get()) &&
           sameTree(a->right.get(), b->right.get());
}
 
void testStrictCodec() {
    StrictCodec codec;
    std::unique_ptr<TreeNode> root;
 
    assert(codec.deserialize(
        "8,6,5,$,$,7,$,$,10,9,$,$,11,$,$,", root));
    assert(root->value == 8);
    assert(root->left->value == 6);
    assert(root->right->right->value == 11);
 
    assert(codec.deserialize("$,", root));
    assert(root == nullptr);
 
    assert(!codec.deserialize("5,$,", root));
    assert(!codec.deserialize("5,x,$,$,", root));
    assert(!codec.deserialize("5,$,$,9,$,$,", root));
}

自动往返还应断言serialize(deserialize(bytes))产生规范化同一字符串，称为。对畸形输入则要断言失败且原output不被部分结果覆盖。

畸形输入测试应按错误类别成组生成：删除合法流任意一个token验证截断；在完整根树后追加数字或$验证尾随数据；把整数替换为空串、字母、只有负号或超范围十进制验证词法检查；生成超过最大深度的连续单链验证资源限制。对每个失败用例，解析器都应返回false、保持调用方旧root不变，并由RAII释放临时节点。

模糊测试可以先随机生成有限树，序列化后执行随机删除、插入和替换，再交给严格解析器。若变异串偶然仍是合法树，不能强行期待失败，而应验证重新序列化得到规范格式且再次解析同构。这样区分“无效输入被拒绝”和“另一份有效树被稳定接受”，避免把随机变异等同于错误标签。

规范化还应规定整数是否允许前导加号、前导零和空白。作者ostream输出不会生成这些形式，严格解析可选择只接受规范十进制，减少同一树对应多种字节表示；若为了兼容放宽读取，写出端仍应只有一种标准形式。

复杂度、深度与安全上限

序列化访问每个真实节点和每个空槽一次，时间O(n)，输出含2n+1个token，字符长度还取决于整数位数。反序列化同样O(n)加数字解析成本，创建n个节点。

递归调用栈O(h)。偏斜树h等于n，可能栈溢出；网络输入可故意构造超深编码。严格解析应设置最大token数、最大深度、单token长度与总字节数，超限即拒绝。

作者buffer只有32字节且i不受限，是内存安全风险；stream>>ch还跳过空白，意味着格式中的空白可能被忽略。协议应明确是否允许空白，最好逐token解析而非逐字符写固定数组。

整数转换要检查正负号、前导形式和范围。from_chars不会接受空字符串并可报告result_out_of_range；若要跨语言稳定，还应规定32位有符号范围和十进制编码。

树契约与版本演进

输入必须是有限无环树。共享子节点的DAG会被序列化为两份独立子树，反序列化后共享身份丢失；成环会无限递归。若要保存对象图身份，需要节点ID和引用token，不是本题格式。

协议升级不能随意把$改成#或删除尾逗号而不考虑旧数据。可在消息前增加版本与长度，或保持解析器向后兼容、序列化器只输出最新规范。

敏感数据持久化还需校验完整性和来源。格式可逆不等于可信；反序列化是资源分配入口，应先限制大小，再构造对象，避免内存耗尽。

正确性证明

对树结构归纳。空树序列化为单个$，解析返回空，正确。非空树先写根值，再递归写左右编码；解析先读同一根值，再按相同顺序分别消费左右子编码。

由归纳假设，左右子树均被唯一恢复。$明确每个递归分支终点，任何token既不遗漏也不跨子树消费。因此反序列化序列化结果得到与原树结构和值相同的树。

反方向上，严格解析完整消费一个合法token流后，再按规范序列化，每个数字和$的位置由恢复树唯一决定，得到相同规范流。

本章练习

练习

问题 1： 为什么序列化需要空节点占位符？

问题 2： 前序序列化如何保证唯一性？

问题 3： 反序列化游标如何管理？

概念说明

本章核心概念包括：前序遍历，空节点占位符。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

  1. 作者使用前序遍历，非空写整数，空节点写$。
  2. 每个token后带逗号，空树规范编码为$,。
  3. 空节点占位符保存拓扑，值序列本身不能唯一恢复树形。
  4. 反序列化游标遇数字构造节点并递归左右，遇$返回空。
  5. 作者ReadStream适合可信示例，不区分截断、错误与合法空标记。
  6. 严格解析要拒绝非法整数、提前结束和尾随token，并自动清理失败前缀。
  7. 时间O(n)、递归空间O(h)，不可信输入还需节点、深度和字节上限。
  8. 六组官方测试中全同值不规则树证明$是结构可逆的关键。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

前序序列化
按前序顺序写出节点值和空位。
占位符
空节点的标记，如 $ 或 null。
流式格式
逐个记号顺序读写的序列化格式。
游标
反序列化时消费 token 的位置指针。
解析器
读取 token 序列恢复树结构的程序。
反序列化
从 token 序列重建二叉树的过程。
复习本章（5 题）

讨论

评论区加载中…