297. 二叉树的序列化与反序列化

Difficulty
Hard
Tags
二叉树
URL
https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
Star
 
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例 1：
notion imagenotion image
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
提示：
  • 树中结点数在范围 [0, 104] 内
  • 1000 <= Node.val <= 1000

分析

一般而言，没法通过单独的前序or后序or中序的结果来重建二叉树，因为不知道空节点在哪。但是如果遍历的时候，把空节点也保存下来即可重建二叉树

法1 递归

思路
如下二叉树，通过前序遍历序列化序列化二叉树，遍历的时候，将空姐点也保存下来。
 
notion imagenotion image
解序列的时候，就按照 序列化的列表值，挨个解就好了，如下图。注意，接序列的时候，列表值是变化的，每遍历一层，列表首值均会被删掉
题解
先序遍历
# 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 is None:
            return ["#"]
        return  [root.val] + self.serialize(root.left) + self.serialize(root.right)
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        # 遍历的时候，data是变化的！！就是说此处pop掉的值就在后面的遍历中不存在了
        head_val = data.pop(0)
        if head_val is '#':
            return None
        node = TreeNode(head_val)
        # 所以 传到以下两个函数的参数是不一样的
        node.left = self.deserialize(data)
        node.right = self.deserialize(data)
        return node

        

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))
后序遍历
后序遍历：
  • 序列化：只需要将当前节点的值加到最后面
  • 反序列化：首先根节点在最后，其次紧挨着根节点的是右子树，所以应该先接右子树再接左子树
# 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 is None:
            return ["#"]
        return  self.serialize(root.left) + self.serialize(root.right) + [root.val]
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        # 遍历的时候，data是变化的！！就是说此处pop掉的值就在后面的遍历中不存在了
        head_val = data.pop()
        if head_val is '#':
            return None
        node = TreeNode(head_val)
        # 所以 传到以下两个函数的参数是不一样的
        node.right = self.deserialize(data)
        node.left = self.deserialize(data)
        return node

        

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))
中序遍历
中序遍历行不通！！
回顾前序、后序，前序遍历根节点在最前面，后序遍历根节点在最后面。而中序遍历根节点被夹在中间根本不知道根节点是哪个

法2 迭代法

思路
迭代法可以有迭代前序、后序。还有层级遍历
迭代前序、后序和递归思路一致较为简单
层级遍历：
  • 序列化：用队列queue辅助来层次遍历二叉树，遍历时将空节点也存进列表result！
  • 反序列化：反序列化的时候，根据一个非空节点必定对应列表两个值(或值或#)，所以按照层次遍历来连接，在遍历过程中当子节点非空时，将子节点存进队列。
💡
第i个非空节点 的两个子节点在列表中的下标一定是 [2*i - 1]和 [2*i] 当然具体值可能为“#”.由于遍历的时候队列只存非空节点，所以很好连接左右子树
二叉树层次遍历序列化结果二叉树层次遍历序列化结果
二叉树层次遍历序列化结果
题解
# 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
        """
        result = []
        if root is None:
            return result
        # queue 辅助层次遍历的队列，只存非空节点，因为存了空节点也没用
        # result 存放序列化结果的列表， 即存非空节点也存空节点
        queue = []
        queue.append(root)
        result.append(root.val)
        while len(queue) > 0:
            cur = queue.pop(0)

            # 存的时候判断，节点为空时，result存# 
            if cur.left:
                queue.append(cur.left)
                result.append(cur.left.val)
            else:
                result.append('#')
            if cur.right:
                queue.append(cur.right)
                result.append(cur.right.val)
            else:
                result.append("#")
        return result


    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if len(data) == 0:
            return None
        # 存进队列的只有非空节点，一个非空节点对应列表的两个值
        root = TreeNode(data[0])
        queue = []
        queue.append(root)
        i = 1 # 因为第0个值给了根节点
        while i < len(data):
            # 从队列取出一个节点作为父节点 （一个父节点消耗两个data列表值）
            parents = queue.pop(0)

            # 连接 父节点 与 左子节点
            left = data[i] 
            i += 1
            if left != '#':
                parents.left = TreeNode(left)
                queue.append(parents.left)
            else:
                parents.left = None

            # 连接父节点 与 右子节点
            right = data[i]
            i += 1
            if right != '#':
                parents.right = TreeNode(right)
                queue.append(parents.right)
            else:
                parents.right = None
        
        return root

        

        

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))
上述代码解序列化也是按照层次遍历的模板来写的，一个非空节点对应data中的两个值，且data中的值是按照顺序往后走的。
因为第i个非空节点 的两个子节点在列表中的下标一定是 [2*i - 1]和 [2*i]。 所以还有如下写法
# 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
        """
        result = []
        if root is None:
            return result
        # queue 辅助层次遍历的队列，只存非空节点，因为存了空节点也没用
        # result 存放序列化结果的列表， 即存非空节点也存空节点
        queue = []
        queue.append(root)
        result.append(root.val)
        while len(queue) > 0:
            cur = queue.pop(0)

            # 存的时候判断，节点为空时，result存# 
            if cur.left:
                queue.append(cur.left)
                result.append(cur.left.val)
            else:
                result.append('#')
            if cur.right:
                queue.append(cur.right)
                result.append(cur.right.val)
            else:
                result.append("#")
        print(f"res{result}")
        return result


    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if len(data) == 0:
            return None
        # 存进队列的只有非空节点，
        # 第i个非空节点 的两个子节点在列表data中的下标一定是 [2*i - 1]和 [2*i]
        root = TreeNode(data[0]) 
        queue = []
        queue.append(root)
        i = 0 # 用来统计第 1 个非空节点
        while len(queue) > 0:
            node = queue.pop(0)
            i += 1   # 第i 个非空节点
            # 连接左子树
            left = data[2*i - 1]
            if left != '#':
                node.left = TreeNode(left)
                queue.append(node.left)
            # 连接 右子树
            right = data[2*i ]
            if right != "#":
                node.right = TreeNode(right)
                queue.append(node.right)
        return root


# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))