牛客3747题解析：二叉树序列化与反序列化（C++实现）

一、题目解读

牛客3747题要求实现二叉树的序列化与反序列化功能。序列化即将二叉树转化为字符串，反序列化则将字符串还原为二叉树结构。题目核心在于设计高效的遍历与节点表示方法，需考虑空节点的处理，确保序列化后的数据能完整还原树结构。

二、解题思路

采用前序遍历+递归策略。序列化时，递归遍历二叉树：若节点为空，用“#”占位；非空节点则记录值并递归处理左右子树。反序列化时，通过字符串流逐字符读取，遇“#”创建空节点，遇数字则创建节点并递归构建子树。关键在于利用特殊字符标记空节点，确保序列化与反序列化的逻辑一致性。

三、解题步骤

1. 序列化（Serialize）：

○ 创建字符串流（stringstream）存储结果。

○ 递归函数serializeHelper：

    若节点为空，写入“#”；否则写入节点值。

    递归处理左子树与右子树。

○ 将流内容转为字符数组并返回。

2. 反序列化（Deserialize）：

○ 将输入字符串转为流，调用deserializeHelper递归构建树。

○ 读取流中字符：若为“#”，返回空；否则创建节点，递归构建左右子树。

○ 返回根节点。

四、代码与注释

class Solution {
private:
    // 序列化辅助函数：递归遍历并写入流
    void serializeHelper(TreeNode* root, stringstream& ss) {
        if (!root) {  // 空节点用“#”标记
            ss << "# ";
            return;
        }
        ss << root->val << " ";  // 非空节点写入值
        serializeHelper(root->left, ss);  // 递归左子树
        serializeHelper(root->right, ss);  // 递归右子树
    }
    
    // 反序列化辅助函数：从流中读取并构建树
    TreeNode* deserializeHelper(stringstream& ss) {
        string val;
        ss >> val;  // 读取下一个字符
        if (val == "#") return nullptr;  // 若为“#”，返回空
        TreeNode* node = new TreeNode(stoi(val));  // 创建节点
        node->left = deserializeHelper(ss);  // 递归构建左子树
        node->right = deserializeHelper(ss);  // 递归构建右子树
        return node;
    }

public:
    // 序列化主函数：调用辅助函数并返回字符数组
    char* Serialize(TreeNode* root) {
        stringstream ss;
        serializeHelper(root, ss);
        string str = ss.str();
        char* res = new char[str.size() + 1];
        strcpy(res, str.c_str());
        return res;
    }
    
    // 反序列化主函数：将字符串转为流并调用辅助函数
    TreeNode* Deserialize(char* str) {
        if (!str) return nullptr;  // 空串直接返回空
        stringstream ss(str);
        return deserializeHelper(ss);
    }
};

五、总结

该解法通过前序遍历结合特殊字符标记，实现了简洁高效的序列化与反序列化。优点：代码结构清晰，递归逻辑易于理解。适用于对空间要求不高但需快速实现的场景，是解决二叉树序列化问题的经典思路。