ITPub博客

首页 > 应用开发 > Python > 刷题系列 - 序列化和反序列化一个二叉树

刷题系列 - 序列化和反序列化一个二叉树

原创 Python 作者:张国平 时间:2020-02-15 01:26:51 0 删除 编辑

序列化和反序列化一个二叉树,是很开放的一题,就是给出一个二叉树,用序列化方法生成一个字符串;然后用反序列化方法把这个字符串生成原来二叉树。这个在编程时候各个类型一般都有序列化的,用于存储。


这里面要用到python中list转化字符串方法 ','.join(list), 和字符串转换为list的方法string.split(',')。


其实可以用之前刷题的几个题目来组合,比如遍历二叉树生成中序和后序两个队列,合并为一个队列,作为序列化方法;然后有一题是按照中序和后序队列生成二叉树,就可以作为反序列化的方法使用。当然,这样会有很多冗余数据。


其实这个题目比较麻烦的地方就是优化,实现倒是很不难。

我这边用了序列化层级遍历,就是从根节点到叶子节点一层层按照从左到用遍历,如果某个节点的左或者右子节点为空,用#号代替;最后叶子节点下面会都是”#“号,这里做了个判断,如果某层都是#号,视作为空,结束遍历。


反序列化采用对应的方法,这里不多说,看代码即可。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if root != None:
            checkList = [root]
        else:
            checkList = []
        AllNodeList = []
        while checkList != []:
            nextList = []
            for Node in checkList:
                if Node != '#':
                    AllNodeList.append(str(Node.val))
                    if Node.left == None:
                        nextList.append('#')
                    else:
                        nextList.append(Node.left)
                    if Node.right == None:
                        nextList.append('#')
                    else:
                        nextList.append(Node.right)
                else:
                    AllNodeList.append(Node)
            if len(set(nextList)) == 1 and '#' in nextList:
                nextList = []
            checkList = nextList
        return ','.join(AllNodeList)
        
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data == '':
            currentLevel = []
            root = None
        else:
            AllNodeList = data.split(",")
            root = TreeNode(int(AllNodeList.pop(0)))
            currentLevel =[root]
        while currentLevel != [] and AllNodeList!= []:
            nextLevel = []
            for node in currentLevel:
                leftValue = AllNodeList.pop(0)
                if leftValue != '#':
                    node.left = TreeNode(int(leftValue))
                    nextLevel.append(node.left)
                    
                rightValue = AllNodeList.pop(0)
                if rightValue != '#':
                    node.right = TreeNode(int(rightValue))
                    nextLevel.append(node.right)
            print([node.val for node in nextLevel])
            currentLevel = nextLevel
        return root  
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))



来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/22259926/viewspace-2675651/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
SAP 金融风险管理产品专家

注册时间:2009-08-05

  • 博文量
    188
  • 访问量
    416777