Python序列化二叉树

本文阅读 2 分钟
首页 Python笔记 正文

最终要实现的是二叉树的序列化和反序列化。首先来看二叉树的序列化,二叉树的序列化就是采用前序遍历二叉树输出节点,再碰到左子节点或者右子节点为None的时候输出一个特殊字符"#"。对于反序列化,就是针对输入的一个序列构建一棵二叉树,我们可以设置一个指针先指向序列的最开始,然后把指针指向位置的数字转化为二叉树的结点,后移一个数字,继续转化为左子树和右子树。当遇到当前指向的字符为特殊字符"#"或者指针超出了序列的长度,则返回None,指针后移,继续遍历。

'''
请实现两个函数,分别用来序列化和反序列化二叉树。这里没有规定序列化的方式。
'''

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def Serialize(self, root):
        serializeStr = ''
        if root == None:
            return '#'
        stack = []
        while root or stack:
            while root:
                serializeStr += str(root.val) + ','
                stack.append(root)
                root = root.left
            serializeStr += '#,'
            root = stack.pop()
            root = root.right
        serializeStr = serializeStr[:-1]
        return serializeStr

    def Deserialize(self, s):
        serialize = s.split(',')
        tree, sp = self.deserialize(serialize, 0)
        return tree

    def deserialize(self, s, sp):
        if sp >= len(s) or s[sp] == '#':
            return None, sp + 1
        node = TreeNode(int(s[sp]))
        sp += 1
        node.left, sp = self.deserialize(s, sp)
        node.right, sp = self.deserialize(s, sp)
        return node, sp
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

Python按之字形顺序打印二叉树
« 上一篇 01-21
Python二叉搜索树的第k个结点
下一篇 » 01-21

发表评论

惪特博客
  • 文章总数:
    18085 篇
  • 评论总数:
    52233 条
  • 标签总数:
    8183 个
  • 总浏览量:
    15794586 次
  • 最后更新:
    7小时前

最多点赞

随便看看

标签TAG