首页 / 算法 / 剑指offer:序列化二叉树
剑指offer:序列化二叉树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了剑指offer:序列化二叉树,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1916字,纯文字阅读大概需要3分钟。
内容图文
![剑指offer:序列化二叉树](/upload/InfoBanner/zyjiaocheng/1063/2336063ba5a34be2b074f4f13b88f622.jpg)
请实现两个函数,分别用来序列化和反序列化二叉树
# -*- coding: utf-8 -*-
# @Time : 2019-07-07 15:48
# @Author : Jayce Wong
# @ProjectName : job
# @FileName : serializeBinaryTree.py
# @Blog : https://blog.51cto.com/jayce1111
# @Github : https://github.com/SysuJayce
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
"""
用先序遍历将二叉树序列化下来,然后再反序列化即可。因为这里的关键在于如何定位到根节点,虽然用后
序遍历也可以定位根节点,但是在反序列化的时候就不容易实现。
"""
def Serialize(self, root):
"""
序列化的时候正常先序遍历二叉树即可,但是为了准确定位到叶子节点,我们需要
**将空节点也序列化下来**
"""
def helper(pRoot, curSerial):
if not pRoot:
# 这里我们用‘$‘表示空节点
curSerial.append(‘$‘)
return
# 用递归方法进行序列化,先将根节点序列化,然后遍历左子树、右子树
curSerial.append(pRoot.val)
helper(pRoot.left, curSerial)
helper(pRoot.right, curSerial)
if not root:
return ‘‘
serialization = []
helper(root, serialization)
return ‘,‘.join(map(str, serialization))
def Deserialize(self, s):
"""
在反序列化的时候,由于构造一个节点的时候默认左右子节点都是空,因此如果字符串中遇到了‘$‘,
可以直接忽略。也就是只需要处理非空节点
"""
def helper(curStr, curRoot):
# 递归出口
if not curStr:
return curRoot
# 这里由于我们使用一个列表保存节点信息,因此可以用pop()来保存剩余待反序列化的节点
curVal = curStr.pop(0)
# 如果是‘$‘,即该节点为空,那么这时候由于输入的curRoot也为空,直接返回即可
if curVal != ‘$‘:
# 从整体来看,我们需要先构造根节点,然后分别构造其左右子节点。
# 递归在确定了出口条件之后,就只需要将整体逻辑写出来就行了。
curRoot = TreeNode(int(curVal))
curRoot.left = helper(curStr, curRoot.left)
curRoot.right = helper(curStr, curRoot.right)
return curRoot
if not s:
return None
s = s.split(‘,‘)
root = helper(s, None)
return root
def printTree(root: TreeNode):
if not root:
return
print(root.val)
printTree(root.left)
printTree(root.right)
def main():
solution = Solution()
root = TreeNode(10)
root.left = TreeNode(6)
root.right = TreeNode(14)
root.left.left = TreeNode(4)
root.left.right = TreeNode(8)
root.right.left = TreeNode(12)
root.right.right = TreeNode(16)
s = solution.Serialize(root)
print(s)
printTree(solution.Deserialize(s))
if __name__ == ‘__main__‘:
main()
原文:https://blog.51cto.com/jayce1111/2417881
内容总结
以上是互联网集市为您收集整理的剑指offer:序列化二叉树全部内容,希望文章能够帮你解决剑指offer:序列化二叉树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。