剑指offer：序列化二叉树

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

# -*- 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/SysuJayceclass TreeNode:    def __init__(self, x):        self.val = x        self.left = None        self.right = Noneclass 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 rootdef 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()