LintCode领扣题解丨谷歌面试题：二叉树的序列化和反序列化

2023-11-16 21:10:46

设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。

如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。

对二进制树进行反序列化或序列化的方式没有限制，LintCode 将您的 serialize 输出作为 deserialize 的输入，它不会检查序列化的结果。

在线测评地址：
https://www.lintcode.com/problem/serialize-and-deserialize-binary-tree/description?utm_source=sc-tianchi-sz0824

样例 1：
输入：{3,9,20,#,#,15,7}
输出：{3,9,20,#,#,15,7}
解释：
二叉树 {3,9,20,#,#,15,7}，表示如下的树结构：

它将被序列化为 {3,9,20,#,#,15,7}
样例 2：
输入：{1,2,3}
输出：{1,2,3}
解释：
二叉树 {1,2,3}，表示如下的树结构：
1
/ \
2 3
它将被序列化为 {1,2,3}
我们的数据是进行 BFS 遍历得到的。当你测试结果 Wrong Answer 时，你可以作为输入调试你的代码。你可以采用其他的方法进行序列化和反序列化。

[题解]
考点：

搜索题解：
serialize()采用 bfs，对当前二叉树搜索，遍历 vector，将当前节点左右儿子依次存入 vector，空节点需要删去。
deserialize()首先切割字符串，然后用 isLeftChild 标记是当前是左右儿子，数字转化为字符串，存为队列首节点的左右儿子。
class Solution {
public:

/**
 * This method will be invoked first, you should design your own algorithm 
 * to serialize a binary tree which denote by a root node to a string which
 * can be easily deserialized by your own "deserialize" method later.
 */
vector<string> split(const string &str, string delim) {
    vector<string> results;
    int lastIndex = 0, index;
    while ((index = str.find(delim, lastIndex)) != string::npos) {
        results.push_back(str.substr(lastIndex, index - lastIndex));
        lastIndex = index + delim.length();
    }
    if (lastIndex != str.length()) {
        results.push_back(str.substr(lastIndex, str.length() - lastIndex));
    }
    return results;
}
string serialize(TreeNode *root) {
    if (root == NULL) {
        return "{}";
    }
    vector<TreeNode *> q;
    q.push_back(root);
    for(int  i = 0; i < q.size(); i++) {
        TreeNode * node = q[i];
        if (node == NULL) {
            continue;
        }
        q.push_back(node->left);
        q.push_back(node->right);
    }
    while (q[q.size() - 1] == NULL) {
            q.pop_back();
    }
    string sb="";
    sb += "{";
    sb += to_string(q[0]->val);
    for (int i = 1; i < q.size(); i++) {
        if (q[i] == NULL) {
            sb += (",#");
        } 
        else {
            sb += ",";
            sb += to_string(q[i]->val);
        }
    }
    sb += "}";
    return sb;
}
/**
 * This method will be invoked second, the argument data is what exactly
 * you serialized at method "serialize", that means the data is not given by
 * system, it's given by your own serialize method. So the format of data is
 * designed by yourself, and deserialize it here as you serialize it in 
 * "serialize" method.
 */
TreeNode * deserialize(string &data) {
    // write your code here
    if (data == "{}") return NULL;
    vector<string> vals = split(data.substr(1, data.size() - 2), ",");
    TreeNode *root = new TreeNode(atoi(vals[0].c_str()));
    queue<TreeNode *> Q;
    Q.push(root);
    bool isLeftChild= true;
    for (int i = 1; i < vals.size(); i++) {
        if (vals[i] != "#") {
            TreeNode *node = new TreeNode(atoi(vals[i].c_str()));
            if (isLeftChild) Q.front()->left = node;
            else Q.front()->right = node;
            Q.push(node);
        }
        if (!isLeftChild) {
            Q.pop();
        }
        isLeftChild = !isLeftChild;
    }
    return root;
}

码农公寓

相关文章