剑指 Offer 37. 序列化二叉树

题目描述

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

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

提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例：

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

链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof
注意：本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

解题思路

序列化（node->str）比较好想，使用层级遍历即可。如果遇到空节点，就往结果字符串中添加null即可。结果字符串所有的值使用逗号隔开，返回值如下所示：

result = '[' + ','.join(result_list) + ']'

反序列化不能使用递归的方法，还要使用层级遍历。为什么呢？
之前递归的方式用代码写出来是：

def dfs(self, i):
        if i >= self.length or self.str_list[i] == "null":
            return None
        node = TreeNode(self.str_list[i])
        node.left = self.dfs(2*i+1)
        node.right = self.dfs(2*i+2)
        return node

这种方式依赖于完全二叉树形式的序列化输入，但我们的序列化输入方式并非如此。
比如下面这个二叉树，序列化为[5,2,3,null,null,2,4,3,1]。可见，3之前并没有null填充，这导致无法使用2×i+1的方式定位。

     5
    / \
   2   3
       / \
      2   4
    / \
   3   1

此时可以使用层级遍历来还原出二叉树。每次从队列pop出来的那两个数，如果不是“null”，就将其作为自己的左子树右子树。

解题代码

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return []
        queue = [root]
        result_list = []
        while queue:
            node = queue.pop(0)
            if not node:
                result_list.append("null")
            else:
                result_list.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
        result = '[' + ','.join(result_list) + ']'
        return result

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        data = str(data)
        if data == '[]':
            return None
        str_list = data[1:-1].split(",")
        root = TreeNode(str_list[0])
        queue = [root]
        i = 1
        while queue:
            node = queue.pop(0)
            if str_list[i] != "null":
                node.left = TreeNode(str_list[i])
                queue.append(node.left)
            i += 1
            if str_list[i] != "null":
                node.right = TreeNode(str_list[i])
                queue.append(node.right)
            i += 1
        return root

执行结果

执行结果：通过
执行用时：556 ms, 在所有 Python3 提交中击败了28.40%的用户
内存消耗：19.8 MB, 在所有 Python3 提交中击败了19.91%的用户