Jianbo Dai's

jz037.序列化二叉树

 
  • Jun 27, 2020

题目链接

如果做过jz007.重建二叉树的话，我们知道可以从前序遍历序列和中序遍历序列中构造出一棵二叉树。受此启发，我们可以先把一棵二叉树序列化成一个前序遍历序列和一个中序遍历序列，然后在反序列化时通过这两个序列重构出二叉树。这种思路有两个缺点：一是该法要求二叉树中不能有数值重复的节点；二是只有当两个序列中所有的数据都读出后才能开始反序列化。如果两个遍历序列的数据是从一个数据流中读出来的，那么可能需要等待较长的时间。

实际上，如果二叉树的序列化是从根节点开始的，那么相应的反序列化在根节点的数值读出来的时候就可以开始了。因此，我们可以根据前序遍历的顺序来序列化二叉树，因为前序遍历是从根节点开始的。在遍历二叉树碰到空节点时，这些空节点化为一个特殊的字符，如“$”。接着，在反序列化的时候用在序列化中产生的序列重建二叉树，如[1, 2, 4, $, $, $, 3, 5, $, $, 6, $, $]，从头开始，第一个数字为1，是根节点的值；接下去读出来的是2，2为1的坐节点；同样的，4为2的左节点；当指到第一个$时，说明4这个节点的左节点为空，此时我们不需要继续新建节点；继续遍历，第二个$为4的右节点。以此类推，当遇到数字时，新增节点并填充数值，链接左右节点，并递归处理各自左右节点，若值不是数字，那么并不新建节点而是直接返回None。这个算法的时间复杂度是O（N），空间复杂度是O（N）。

 # 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
        """
        res = []
        def dfs(root):
            if not root:
                res.append("$")
                return 
            res.append(root.val)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return res 

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        l = data[::-1]
        def construct(val):
            if val == "$":
                return None
            else:
                node = TreeNode(val)
                node.left = construct(l.pop())
                node.right = construct(l.pop())
                return node
        return construct(l.pop())

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
Search