剑指 Offer 37. 序列化二叉树 - leetcode 剑指offer系列
发布日期:2021-06-29 07:12:11
浏览次数:4
分类:技术文章
本文共 2325 字,大约阅读时间需要 7 分钟。
题目难度: 困难
今天继续更新剑指 offer 系列, 这道题是一道非常灵活的设计题目, 这里提供一种非常容易理解的方法抛砖引玉, 大家有其他的好方法也欢迎私信我一起交流哦
老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
题目描述
请实现两个函数,分别用来序列化和反序列化二叉树。
题目样例
示例
你可以将以下二叉树:
1 / \ 2 3 / \ 4 5
序列化为 “[1,2,3,null,null,4,5]”
题目思考
- 如何定位节点之间的关系?
解决方案
思路
- 既然题目没有限制序列化和反序列化的算法, 我们就怎样简单怎样来
- 如果我们给每个节点一个唯一的下标, 同时保存它的父节点下标, 以及父节点对当前节点的指向(即左还是右子节点), 当然还有节点本身的值, 这样就能唯一确定整棵树了
- 根据这个思路, 我们序列化的时候就可以使用 BFS, 用一个四元组保存上述信息, 最后转成字符串即可
- 反序列化就更简单了: 使用字典保存下标到值的映射关系(下标唯一), 因为保存的时候是 BFS 逐层遍历的, 所以当要转换某个节点时, 其父节点一定已经转换好并保存在字典中了, 这样就能拿到父节点, 再根据指向决定当前是左还是右子节点即可
- 下面的代码对必要的步骤都有详细的解释, 方便大家理解
复杂度
- 时间复杂度
O(N)
- 每个节点只需要遍历一次
- 空间复杂度
O(N)
- 队列的消耗, 因为是四元组, 所以是
O(4*N) = O(N)
- 队列的消耗, 因为是四元组, 所以是
代码
class Codec: def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ if not root: return '' # 注意这里用List而不是Tuple存四元组, 用于下标赋值 q = [[0, -1, 'L', root]] i = 1 for t in q: # 此处只需要关心当前节点下标, 以及当前节点自身即可, 不用管当前节点的父节点和父节点指向 p, _, _, node = t if node.left: q.append([i, p, 'L', node.left]) i += 1 if node.right: q.append([i, p, 'R', node.right]) i += 1 def convertToStr(t): # 将节点转成对应的值 t[3] = t[3].val # 然后将当前四元组转成字符串 return ','.join(str(x) for x in t) q = [convertToStr(t) for t in q] # 最后将数组转成字符串, 注意此处的分隔符要和上面的四元组分隔符区分开来 return '+'.join(q) def deserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ if not data: return None # 拆分成字符串数组 data = data.split('+') maps = { } root = None for t in data: # 进一步拆分出四元组 i, p, direction, val = t.split(',') node = TreeNode(int(val)) if i == '0': # 保存根节点 root = node # 将当前节点存入字典中 maps[i] = node if p in maps: # 父节点存在, 更新指向关系 parent = maps[p] if direction == 'L': parent.left = node else: parent.right = node return root
大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
转载地址:https://blog.csdn.net/zjulyx1993/article/details/107521165 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月14日 11时48分26秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
把数据存储到外部SD卡上
2019-04-29
实现记住密码功能
2019-04-29
Android数据存储和访问—书籍的增删检查
2019-04-29
网络图片查看器
2019-04-29
健康栏目
2019-04-29
百度地图上定位自己所在的位置
2019-04-29
天气预报
2019-04-29
简单重力感应跑步测速应用
2019-04-29
深度学习之TensorFlow 第三章基本开发步骤--以逻辑回归拟合二维数据为例
2019-04-29
H264码流中SPS PPS详解
2019-04-29
Android Studio cmake编译FFmpeg以及Jni调用
2019-04-29
live555搭建简易流媒体服务
2019-04-29
英伟达CUVID硬解,并通过FFmpeg读取文件
2019-04-29
【Arduino实战教程 001】入门Hello World
2019-04-29
Ubuntu下安装clang和libc++
2019-04-29
RTMP协议播放流程的实现及抓包分析
2019-04-29
在Ubuntu下搭建C/C++编程环境(vim+gcc+gdb)
2019-04-29
C++笔试面试真题回顾与知识点总结
2019-04-29