剑指offer第二版（Python3）--面试题37 : 序列化二叉树

第2章 面试需要的基础知识

第3章 高质量的代码

第4章 解决面试题的思路

  面试题27:二叉树的镜像

  面试题29:顺时针打印矩阵

  面试题30 :包含min函数的栈

  面试题31:栈的压入、弹出序列

  面试题32:上往下打印二叉树

  面试题33: 二叉搜索树的后序遍历序列

  面试题34: 二叉树中和为某一值的路径

  面试题35: 复杂链表的复制

  面试题36：二叉搜索树与双向链表

  面试题37：序列化二叉树

  面试题38：字符串的排列

第5章 优化时间和空间效率

第6章 面试中的各项能力

第7章 两个面试案例

题目描述

牛客网

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

  二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

  二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

解题思路

  序列化二叉树可用前序遍历。

  反序列化：具体思路是按前序遍历“根左右”的顺序，根节点位于其左右子节点的前面，即非空（#）的第一个节点是某子树的根节点，左右子节点在该根节点后，以空节点#为分隔符。先寻找其左节点，直到遇到‘#’，然后寻找其右节点，遇到‘#’则返回。

实战

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return '#'
        # 前序遍历
        def core(node):
            if not node:
                res.append('#')
                return 
            res.append(str(node.val))
            core(node.left)
            core(node.right)
        
        res = []
        core(root)
        return '!'.join(res)
            
    def Deserialize(self, s):
        # write code here
        if not s:
            return None
        nodes = s.split('!')
        
        def core(num):
            if num == '#':
                return
            root = TreeNode(int(num))  # 要记得将字符转为数字！！！
            if nodes:
                root.left = core(nodes.pop(0))
                root.right = core(nodes.pop(0))
            return root