二叉树的序列化和反序列化C++

二叉树的序列化和反序列化是将一棵二叉树的状态转换为一个字符串，然后又恢复成原来的二叉树的过程，通常用于数据存储和在网络中传输。在C++中，我们可以使用自定义的数据结构和迭代方法来实现这个功能。

**序列化（Serialization）**：
1. 定义一个序列化的格式，常见的如前序遍历（根-左-右）或中序遍历（左-根-右）的字符串表示。
2. 创建一个函数，接受二叉树的根节点作为输入，使用递归的方式访问每个节点，并将其值和子节点信息添加到序列中。如果节点为空，可以用特殊标记（如“#”或“null”）表示。
3. 返回最终序列化的字符串。

string serialize(TreeNode* root) {
    // 假设使用前序遍历
    stack<TreeNode*> nodes;
    nodes.push(root);
    string result = "";
    while (!nodes.empty()) {
        TreeNode* node = nodes.top();
        nodes.pop();
        if (node) {
            result += to_string(node->val) + ',';
            nodes.push(node->left);
            nodes.push(node->right);
        } else {
            result += "#,";
        }
    }
    return result.substr(0, result.length() - 1); // 去掉末尾逗号
}

**反序列化（Deserialization）**：
1. 创建一个函数，接受一个字符串作为输入，恢复成二叉树。首先，从字符串中分割出节点值和子节点信息。
2. 用堆栈或队列模拟前序或中序遍历的过程，根据节点值创建新的节点，并将它们连接起来。
3. 当遇到“#”或“null”时，表示当前节点为空，停止添加子节点。

TreeNode* deserialize(string data) {
    if (data == "") return nullptr;

    stack<TreeNode*> nodes;
    char* token = strtok(data.c_str(), ",");
    while (token != nullptr) {
        int val = stoi(token);
        if (isdigit(val)) {
            // 创建新节点并入栈
            TreeNode* node = new TreeNode(val);
            nodes.push(node);
            if (nodes.top()->left == nullptr) {
                nodes.top()->left = nodes.top()->right = nullptr; // 初始化为 null
            } else {
                TreeNode* parent = nodes.top();
                if (parent->left == nullptr) {
                    parent->left = node;
                } else {
                    parent->right = node;
                }
            }
        } else {
            nodes.top()->left = deserialize(next_token);
            nodes.top()->right = deserialize(next_token);
            token = strtok(nullptr, ",");
        }
    }
    return nodes.top();
}