牛客3747题解：二叉树序列化与反序列化完全指南
一、问题背景
牛客3747题要求实现二叉树的序列化与反序列化功能，这是数据结构中的经典问题。序列化将二叉树转换为字符串表示，反序列化则将字符串还原为二叉树结构。
二、核心算法解析
三、完整代码实现（带详细注释）
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);
}
};四、关键知识点详解
五、常见问题解答
Q: 为什么选择前序遍历？ A: 前序遍历序列化可以保持根节点在序列最前，便于重建
Q: 如何处理重复节点值？ A: 通过树的结构信息而非仅靠节点值来保证正确重建
Q: 空节点标记为什么需要空格分隔？ A: 确保多位数节点值能被正确解析
原创内容 转载请注明出处
