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

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

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

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

对二进制树进行反序列化或序列化的方式没有限制,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

它将被序列化为 {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;
}

};
更多题解参见九章算法官网:
https://www.jiuzhang.com/solution/serialize-and-deserialize-binary-tree/?utm_source=sc-tianchi-sz0824

相关文章
|
1月前
|
JSON 数据格式 索引
Python中序列化/反序列化JSON格式的数据
【11月更文挑战第4天】本文介绍了 Python 中使用 `json` 模块进行序列化和反序列化的操作。序列化是指将 Python 对象(如字典、列表)转换为 JSON 字符串,主要使用 `json.dumps` 方法。示例包括基本的字典和列表序列化,以及自定义类的序列化。反序列化则是将 JSON 字符串转换回 Python 对象,使用 `json.loads` 方法。文中还提供了具体的代码示例,展示了如何处理不同类型的 Python 对象。
|
1月前
|
存储 安全 Java
Java编程中的对象序列化与反序列化
【10月更文挑战第22天】在Java的世界里,对象序列化和反序列化是数据持久化和网络传输的关键技术。本文将带你了解如何在Java中实现对象的序列化与反序列化,并探讨其背后的原理。通过实际代码示例,我们将一步步展示如何将复杂数据结构转换为字节流,以及如何将这些字节流还原为Java对象。文章还将讨论在使用序列化时应注意的安全性问题,以确保你的应用程序既高效又安全。
|
2月前
|
存储 Java
Java编程中的对象序列化与反序列化
【10月更文挑战第9天】在Java的世界里,对象序列化是连接数据持久化与网络通信的桥梁。本文将深入探讨Java对象序列化的机制、实践方法及反序列化过程,通过代码示例揭示其背后的原理。从基础概念到高级应用,我们将一步步揭开序列化技术的神秘面纱,让读者能够掌握这一强大工具,以应对数据存储和传输的挑战。
|
2月前
|
存储 安全 Java
Java编程中的对象序列化与反序列化
【10月更文挑战第3天】在Java编程的世界里,对象序列化与反序列化是实现数据持久化和网络传输的关键技术。本文将深入探讨Java序列化的原理、应用场景以及如何通过代码示例实现对象的序列化与反序列化过程。从基础概念到实践操作,我们将一步步揭示这一技术的魅力所在。
|
1月前
|
存储 缓存 NoSQL
一篇搞懂!Java对象序列化与反序列化的底层逻辑
本文介绍了Java中的序列化与反序列化,包括基本概念、应用场景、实现方式及注意事项。序列化是将对象转换为字节流,便于存储和传输;反序列化则是将字节流还原为对象。文中详细讲解了实现序列化的步骤,以及常见的反序列化失败原因和最佳实践。通过实例和代码示例,帮助读者更好地理解和应用这一重要技术。
35 0
|
1月前
|
算法 Java
JAVA 二叉树面试题
JAVA 二叉树面试题
17 0
|
3月前
|
JSON 安全 编译器
扩展类实例的序列化和反序列化
扩展类实例的序列化和反序列化
39 1
|
3月前
|
JSON fastjson Java
niubility!即使JavaBean没有默认无参构造器,fastjson也可以反序列化。- - - - 阿里Fastjson反序列化源码分析
本文详细分析了 Fastjson 反序列化对象的源码(版本 fastjson-1.2.60),揭示了即使 JavaBean 沲有默认无参构造器,Fastjson 仍能正常反序列化的技术内幕。文章通过案例展示了 Fastjson 在不同构造器情况下的行为,并深入探讨了 `ParserConfig#getDeserializer` 方法的核心逻辑。此外,还介绍了 ASM 字节码技术的应用及其在反序列化过程中的角色。
91 10
|
3月前
|
存储 XML JSON
用示例说明序列化和反序列化
用示例说明序列化和反序列化
21 1
|
3月前
|
存储 Java 开发者
Java编程中的对象序列化与反序列化
【9月更文挑战第20天】在本文中,我们将探索Java编程中的一个核心概念——对象序列化与反序列化。通过简单易懂的语言和直观的代码示例,你将学会如何将对象状态保存为字节流,以及如何从字节流恢复对象状态。这不仅有助于理解Java中的I/O机制,还能提升你的数据持久化能力。准备好让你的Java技能更上一层楼了吗?让我们开始吧!