序列化二叉树

更多题解，欢迎关注公众号【程序员学长】，欢迎加入

问题描述

剑指 Offer 37. 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例：

输入：root = [1，2，3，null，null，4，5]

输出：[1，2，3，null，null，4，5]

分析问题

我们都知道对于不同的二叉树进行先序、中序、后序或者层序遍历得到的遍历结果有可能是相同的，即如果知道了遍历序列，我们不能确定唯一的一颗二叉树，而题目要求的序列化和反序列化是一对可逆操作，即对一棵树进行序列化后，我们还能通过序列化后的结果反序列化还原成原来的那棵树。所以我们需要对二叉树的遍历过程改造一下，这里以层序遍历为例。在遍历的过程中，为了完整的表示二叉树，考虑将叶节点下的 null 也记录。下面我们来看一下具体的实现。

序列化

我们可以借助队列来实现二叉树的层序遍历，在层序遍历的过程中，我们把越过叶子节点的null也加入序列化的结果中。具体算法流程如下所示：

如果给定的二叉树为空，直接返回"[]"
初始化一个队列queue，并把根节点加入。
对二叉树进行层序遍历。当队列为空时跳出。
- 节点出队，记为node。
- 如果node不为空，将node.val加入结果列表中，并且将node的左、右子节点入队。如果node为空，将“null”加入结果列表中。
拼接结果列表，用 ',' 隔开，首尾添加中括号；并将其返回。

序列化二叉树

反序列化

利用队列按层构建二叉树。具体算法流程如下所示：

如果data为空，直接返回null。
初始化列表vals（去掉首尾括号，再用逗号隔开），指针 i = 1 ，将根节点 root （值为 vals[0] ）入队；
按层构建二叉树，当队列为空时跳出；
- 节点出队，记为node。
- 构建 node 的左子节点，node.left 的值为 vals[i] ，并将 node.left 入队；然后执行i=i+1。
- 构建 node 的右子节点，node.right 的值为 vals[i] ，并将 node.right 入队；然后执行i=i+1。
返回根节点 root 即可。

序列化二叉树

下面我们来看一下代码的实现。

class Codec:
    def serialize(self, root):
        #如果二叉树为空，直接返回"[]"
        if not root:
            return "[]"
        #初始化一个队列
        queue = collections.deque()
        #将根节点加入队列中
        queue.append(root)
        #结果列表
        res = []
        #记录null的个数，遇到非空节点就将之前的null节点加入到结果列表中
        null_count=0

        while queue:
            node = queue.popleft()
            if node:
                #遇到非空节点就将之前的null节点加入到结果列表中
                if null_count != 0:
                    res.extend(["null"] * null_count)
                    null_count=0

                res.append(str(node.val))
                #node的左、右子节点入队
                queue.append(node.left)
                queue.append(node.right)
            else:
                #记录null节点的个数
                null_count=null_count+1

        return '[' + ','.join(res) + ']'

    def deserialize(self, data):
        #如果data为"[]",代表二叉树是空，直接返回
        if data == "[]":
            return
        #初始化
        vals = data[1:-1].split(',')
        i=1
        #初始化根节点，并将其入队
        root = TreeNode(int(vals[0]))
        queue = collections.deque()
        queue.append(root)

        while queue:
            if i>=len(vals):
                break
            node = queue.popleft()
            #添加左子节点
            if vals[i] != "null":
                node.left = TreeNode(int(vals[i]))
                queue.append(node.left)
            i += 1
            if i>=len(vals):
                break
            #添加右子节点
            if vals[i] != "null":
                node.right = TreeNode(int(vals[i]))
                queue.append(node.right)
            i += 1
        return root