牛客3747题解：二叉树序列化与反序列化完全指南

一、问题背景

牛客3747题要求实现二叉树的序列化与反序列化功能，这是数据结构中的经典问题。序列化将二叉树转换为字符串表示，反序列化则将字符串还原为二叉树结构。

二、核心算法解析

1. 前序遍历序列化：采用根-左-右的遍历顺序

2. 特殊标记处理：使用"#"表示空节点

3. 递归重建：通过递归方式重建二叉树结构

三、完整代码实现（带详细注释）

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 NULL;  // 空节点处理
        
        // 创建新节点并递归构建子树
        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());  // 转换为C风格字符串
        return res;
    }
    
    // 反序列化接口
    TreeNode* Deserialize(char *str) {
        if (!str) return NULL;  // 空指针检查
        stringstream ss(str);  // 从字符串初始化流
        return deserializeHelper(ss);
    }
};

四、关键知识点详解

1. stringstream的使用：

• 提供内存中的字符串流操作

• 自动处理空格分隔的输入输出

2. 递归的应用：

• 序列化时深度优先遍历

• 反序列化时按相同顺序重建

3. 内存管理：

• 动态分配char数组存储结果

• 需要调用者负责释放内存

五、常见问题解答

Q: 为什么选择前序遍历？ A: 前序遍历序列化可以保持根节点在序列最前，便于重建

Q: 如何处理重复节点值？ A: 通过树的结构信息而非仅靠节点值来保证正确重建

Q: 空节点标记为什么需要空格分隔？ A: 确保多位数节点值能被正确解析