leetcode297：二叉树的序列化与反序列化

题目链接

leetcode

题目描述

序列化是将一个数据结构或对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

const int NULL_NODE = -1001;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i ++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i ++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    1.深度优先搜索
    二叉树的序列化本质上是对其值进行编码，可以通过遍历树来完成。
    深度优先搜索可以从一个根开始，一直延伸到某个叶，然后回到根，到达另一个分支。
    按照根结点、左结点和右结点之间的相对顺序，将深度优先搜索策略分为：
        先序遍历、中序遍历、后序遍历
    
    2.广度优先遍历（层次遍历）
*/

/*
    先序遍历
*/
class Codec {
public:
    // 主函数：将二叉树序列化为字符串
    string serialize(TreeNode* root) {
        string res;
        serializeCode(root, res);
        return res;
    }

    // 主函数：将字符串反序列化为二叉树
    TreeNode* deserialize(string data) {
        // 将字符串转化为列表
        queue<string> nodes = split(data, ',');
        return deserializeCode(nodes);
    }

    // 辅助函数：将二叉树存入字符串 str
    void serializeCode(TreeNode* root, string& str) {
        if (root == nullptr) {
            str += "#,";
            return;
        }

        // 先序遍历
        str += to_string(root->val) + ",";
        serializeCode(root->left, str);
        serializeCode(root->right, str);
    }

    // 辅助函数：通过 nodes 列表构造二叉树
    TreeNode* deserializeCode(queue<string>& nodes) {
        if (nodes.empty()) return nullptr;

        // 先序遍历
        string first = nodes.front(); nodes.pop();
        if (first == "#") return nullptr;
        TreeNode* root = new TreeNode(stoi(first));
        root->left = deserializeCode(nodes);
        root->right = deserializeCode(nodes);

        return root;
    }

    queue<string> split(string& str, char c) {
        queue<string> items;
        for (int i = 0; i < str.size(); i ++) {
            int j = i;
            string item;
            while (str[j] != c) {
                item += str[j ++];
            }
            i = j;
            items.push(item);
        }

        return items;
    }
};

/*
    中序遍历

    结论：中序遍历的方式不行，因为无法实现反序列化方法 deserialize。
    序列化方法 serialize 容易，把字符串的拼接操作放到中序遍历的位置就行。
*/

/*
    后序遍历
*/
class Codec_1 {
public:
    // 主函数：将二叉树序列化为字符串
    string serialize(TreeNode* root) {
        string res;
        serializeCode(root, res);
        return res;
    }

    // 主函数：将字符串反序列化为二叉树
    TreeNode* deserialize(string data) {
        // 将字符串转化为列表
        deque<string> nodes = split(data, ',');
        return deserializeCode(nodes);
    }

    // 辅助函数：将二叉树存入字符串 str
    void serializeCode(TreeNode* root, string& str) {
        if (root == nullptr) {
            str += "#,";
            return;
        }

        // 后序遍历
        serializeCode(root->left, str);
        serializeCode(root->right, str);
        str += to_string(root->val) + ",";
    }

    // 辅助函数：通过 nodes 列表构造二叉树
    TreeNode* deserializeCode(deque<string>& nodes) {
        if (nodes.empty()) return nullptr;

        // 后序遍历
        string last = nodes.back(); nodes.pop_back();
        if (last == "#") return nullptr;
        TreeNode* root = new TreeNode(stoi(last));
        // 先构造右子树，后构造左子树
        root->right = deserializeCode(nodes);
        root->left = deserializeCode(nodes);

        return root;
    }

    deque<string> split(string& str, char c) {
        deque<string> items;
        for (int i = 0; i < str.size(); i ++) {
            int j = i;
            string item;
            while (str[j] != c) {
                item += str[j ++];
            }
            i = j;
            items.push_back(item);
        }

        return items;
    }
};

/*
    层次遍历
*/
class Codec_2 {
public:
    // 主函数：将二叉树序列化为字符串
    string serialize(TreeNode* root) {
        if (root == nullptr) return "";

        string res;
        // 初始化队列，将 root 加入队列
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front(); q.pop();
            if (node == nullptr) {
                res += "#,";
                continue;
            }
            res += to_string(node->val) + ",";
            q.push(node->left);
            q.push(node->right);
        }

        return res;
    }

    // 主函数：将字符串反序列化为二叉树
    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;

        vector<string> nodes = split(data, ',');
        TreeNode* root = new TreeNode(stoi(nodes[0]));
        // 初始化队列，将 root 加入队列
        queue<TreeNode*> q;
        q.push(root);
        for (int i = 1; i < nodes.size(); ) {
            // 队列中保存的结点
            TreeNode* node = q.front(); q.pop();
            // 该结点的左子结点
            string left = nodes[i ++];
            if (left != "#") {
                node->left = new TreeNode(stoi(left));
                q.push(node->left);
            } else {
                node->left = nullptr;
            }
            // 该结点的右子结点
            string right = nodes[i ++];
            if (right != "#") {
                node->right = new TreeNode(stoi(right));
                q.push(node->right);
            } else {
                node->right = nullptr;
            }
        }

        return root;
    }

    vector<string> split(string& str, char c) {
        vector<string> items;
        for (int i = 0; i < str.size(); i ++) {
            int j = i;
            string item;
            while (str[j] != c) {
                item += str[j ++];
            }
            i = j;
            items.push_back(item);
        }

        return items;
    }
};

// 测试函数 main
int main() {
    // 示例输入
    Codec codec;
    vector<int> nums = {1, 2, 3, NULL_NODE, 4, 5};

    // 创建二叉树
    TreeNode* root = createTree(nums);

    // 序列化二叉树
    string serialized = codec.serialize(root);
    // 反序列化二叉树
    TreeNode* deserialized = codec.deserialize(serialized);

    // 打印序列化结果
    cout << "Serialized: " << serialized << endl;
    // 打印反序列化结果
    cout << "Deserialized: ";
    levelOrderTraversal(deserialized);

    // 释放内存
    deleteTree(root);
    deleteTree(deserialized);

    return 0;    
}