温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

剑指offer:序列化二叉树

发布时间:2020-05-17 06:23:49 来源:网络 阅读:528 作者:Jayce_SYSU 栏目:编程语言

题目描述
请实现两个函数,分别用来序列化和反序列化二叉树

# -*- 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()
向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI