LeetCode每日一题——449. 序列化和反序列化二叉搜索树

简介: 序列化是将数据结构或对象转换为一系列位的过程,以便它可以存储在文件或内存缓冲区中,或通过网络连接链路传输,以便稍后在同一个或另一个计算机环境中重建。

题目

序列化是将数据结构或对象转换为一系列位的过程,以便它可以存储在文件或内存缓冲区中,或通过网络连接链路传输,以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串,并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

示例

示例 1:

输入:root = [2,1,3]

输出:[2,1,3]

示例 2:

输入:root = []

输出:[]

思路

树的正反序列化问题:

正序列化:只需要进行树的深度优先遍历即可得到,具体使用何种深度优先遍历方法看题目要求,本题的正序列化应当使用先序遍历

反序列化:一般树的反序列化只有在知道先序和中序或者后序和中序的序列后才能确定一棵树的完整结构。但是本题是一个二叉搜索树,具有一定规律(即左子树的值都比根节点上的值小,右子树上的值都比根节点上的值大)

具体反序列的方法:

将 data 根据分隔符 , 进行分割,假设分割后数组 res 长度为 n,那么 res[0, n - 1]代表完整的子树,我们可以利用「二叉树」特性递归构建,设计递归函数 TreeNode process2(int l, int r, Sring[] res),其含义为利用 res[l, r] 连续段构造二叉树,并返回头结点:

步骤

  • res[l]为头结点,其值为 t,在 [l, r] 范围内找到第一个比 t 大的位置 j:
  • res[l] 的左子树的所有值均比 t 小,且在 data 中连续存储,我们可以递归处理 [l + 1, j -1] 构建左子树;
  • res[l]的右子树的所有值均比 t 大,且在 data 中连续存储,我们可以递归处理 [j,r] 构建右子树。

题解

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Codec:
    def serialize(self, root: TreeNode) -> str:
        """Encodes a tree to a single string.
        """
        return str(self.process(root, []))
    def process(self, root, res):
        if root is None:
            return
        res.append(root.val)
        self.process(root.left, res)
        self.process(root.right, res)
        return res
    def deserialize(self, data: str) -> TreeNode:
        """Decodes your encoded data to tree.
        """
        if data == 'None':
            return None
        else:
            data  = list(data.strip('[').strip(']').split(','))
            return self.process2(0, len(data)-1, data)
    def process2(self,l, r, res):
        if l > r:
            return None
        j,t = l+1, int(res[l])
        ans = TreeNode(t)
        while j <= r and int(res[j]) <= t:
            j += 1
        ans.left = self.process2(l + 1, j-1, res)
        ans.right = self.process2(j, r, res)
        return ans
# Your Codec object will be instantiated and called as such:
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ans
目录
相关文章
|
4月前
|
存储 安全 IDE
说一说序列化与反序列化中存在的问题
本文详细解析了Java中的序列化机制,包括序列化的概念、实现方式及应用场景。通过Student类的实例演示了对象的序列化与反序列化过程,并分析了`Serializable`接口的作用以及`serialVersionUID`的重要意义。此外,文章还探讨了如何通过自定义`readObject()`方法增强序列化的安全性,以及解决可序列化单例模式中可能产生的多实例问题。最后提供了代码示例和运行结果,帮助读者深入理解序列化的原理与实践技巧。
118 2
|
4月前
|
JSON JavaScript 前端开发
Go语言JSON 序列化与反序列化 -《Go语言实战指南》
本文介绍了 Go 语言中使用 `encoding/json` 包实现 JSON 与数据结构之间的转换。内容涵盖序列化(`Marshal`)和反序列化(`Unmarshal`),包括基本示例、结构体字段标签的使用、控制字段行为的标签(如 `omitempty` 和 `-`)、处理 `map` 和切片、嵌套结构体序列化、反序列化未知结构(使用 `map[string]interface{}`)以及 JSON 数组的解析。最后通过表格总结了序列化与反序列化的方法及类型要求,帮助开发者快速掌握 JSON 数据处理技巧。
|
10月前
|
JSON 数据格式 索引
Python中序列化/反序列化JSON格式的数据
【11月更文挑战第4天】本文介绍了 Python 中使用 `json` 模块进行序列化和反序列化的操作。序列化是指将 Python 对象(如字典、列表)转换为 JSON 字符串,主要使用 `json.dumps` 方法。示例包括基本的字典和列表序列化,以及自定义类的序列化。反序列化则是将 JSON 字符串转换回 Python 对象,使用 `json.loads` 方法。文中还提供了具体的代码示例,展示了如何处理不同类型的 Python 对象。
340 1
|
10月前
|
存储 安全 Java
Java编程中的对象序列化与反序列化
【10月更文挑战第22天】在Java的世界里,对象序列化和反序列化是数据持久化和网络传输的关键技术。本文将带你了解如何在Java中实现对象的序列化与反序列化,并探讨其背后的原理。通过实际代码示例,我们将一步步展示如何将复杂数据结构转换为字节流,以及如何将这些字节流还原为Java对象。文章还将讨论在使用序列化时应注意的安全性问题,以确保你的应用程序既高效又安全。
|
11月前
|
存储 Java
Java编程中的对象序列化与反序列化
【10月更文挑战第9天】在Java的世界里,对象序列化是连接数据持久化与网络通信的桥梁。本文将深入探讨Java对象序列化的机制、实践方法及反序列化过程,通过代码示例揭示其背后的原理。从基础概念到高级应用,我们将一步步揭开序列化技术的神秘面纱,让读者能够掌握这一强大工具,以应对数据存储和传输的挑战。
|
11月前
【LeetCode 45】701.二叉搜索树中的插入操作
【LeetCode 45】701.二叉搜索树中的插入操作
63 1
|
10月前
|
存储 缓存 NoSQL
一篇搞懂!Java对象序列化与反序列化的底层逻辑
本文介绍了Java中的序列化与反序列化,包括基本概念、应用场景、实现方式及注意事项。序列化是将对象转换为字节流,便于存储和传输;反序列化则是将字节流还原为对象。文中详细讲解了实现序列化的步骤,以及常见的反序列化失败原因和最佳实践。通过实例和代码示例,帮助读者更好地理解和应用这一重要技术。
472 0
|
11月前
【LeetCode 48】108.将有序数组转换为二叉搜索树
【LeetCode 48】108.将有序数组转换为二叉搜索树
102 0
|
11月前
【LeetCode 47】669.修剪二叉搜索树
【LeetCode 47】669.修剪二叉搜索树
57 0
|
11月前
【LeetCode 46】450.删除二叉搜索树的节点
【LeetCode 46】450.删除二叉搜索树的节点
108 0