剑指37：序列化二叉树

传送门

nowcoder
leetcode

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串。序列化时通过某种符号表示空节点（#）、结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

C++ 代码 - nowcoder

/*
    实现方式：先序遍历
*/
class Solution {
public:
    char* Serialize(TreeNode *root) {    
        string serializeStr = SerializeCore(root);
        char* chs = new char[serializeStr.size()];
        for (int i = 0; i < serializeStr.size(); i ++) {
            chs[i] = serializeStr[i];
        }
        return chs;
    }

    TreeNode* Deserialize(char *str) {
        return DeserializeCore(str);
    }

    string SerializeCore(TreeNode* root) {
        if (root == nullptr) {
            return "#!";
        }

        string str;
        // 先序遍历
        str = to_string(root->val) + "!";
        str += SerializeCore(root->left);
        str += SerializeCore(root->right);
        return str;
    }

    TreeNode* DeserializeCore(char*& str) {
        if (*str == '#') {
            str ++;
            return nullptr;
        }

        int num = 0;
        while (*str != '!') {
            num = num * 10 + *str - '0';
            str ++;
        }

        // 先序遍历
        TreeNode* node = new TreeNode(num);
        node->left = DeserializeCore(++ str);
        node->right = DeserializeCore(++ str); 
        return node;
    }
};

C++ 代码 - leetcode

/*
    实现方式：先序遍历
    注意：有负数的限制
*/
class Codec {
public:
    // 主函数，将二叉树序列化为字符串
    string serialize(TreeNode* root) {
        string res;
        serializeCore(root, res);
        return res;
    }

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

    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;
    }

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

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

    // 辅助函数，通过 nodes 列表构造二叉树
    TreeNode* deserializeCore(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 = deserializeCore(nodes);
        root->right = deserializeCore(nodes);

        return root;
    }
};

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

/*
	实现方式：后序遍历 
*/
class Codec {
public:
    // 主函数，将二叉树序列化为字符串
    string serialize(TreeNode* root) {
        string res;
        serializeCore(root, res);
        return res;
    }

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

    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;
    }

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

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

    // 辅助函数，通过 nodes 列表构造二叉树
    TreeNode* deserializeCore(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 = deserializeCore(nodes);
        root->left = deserializeCore(nodes);

        return root;
    }
};

/*
	实现方式：层次遍历
*/
class Codec {
public:
    // 将二叉树序列化为字符串
    string serialize(TreeNode* root) {
        if (root == nullptr) return "";

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

        return res;
    }

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

        vector<string> nodes = split(data, ',');
        TreeNode* root = new TreeNode(stoi(nodes[0]));
        // 队列 q 记录父节点，将 root 加入队列
        queue<TreeNode*> q;
        q.push(root);
        for (int i = 1; i < nodes.size(); ) {
            // 队列中保存的是父节点
            TreeNode* parent = q.front(); q.pop();

            // 父节点对应的左侧子节点
            string left = nodes[i ++];
            if (left != "#") {
                parent->left = new TreeNode(stoi(left));
                q.push(parent->left);
            } else {
                parent->left = nullptr;
            }

            // 父节点对应的右侧子节点
            string right = nodes[i ++];
            if (right != "#") {
                parent->right = new TreeNode(stoi(right));
                q.push(parent->right);
            } else {
                parent->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;
    }
};