乐趣区

关于leetcode:序列化二叉树

jiezi

序列化二叉树

更多题解，欢送关注公众号【程序员学长】，欢送退出

问题形容

剑指 Offer 37. 序列化二叉树

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

示例：

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

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

剖析问题

咱们都晓得对于不同的二叉树进行先序、中序、后序或者层序遍历失去的遍历后果有可能是雷同的，即如果晓得了遍历序列，咱们不能确定惟一的一颗二叉树，而题目要求的序列化和反序列化是一对可逆操作，即对一棵树进行序列化后，咱们还能通过序列化后的后果反序列化还原成原来的那棵树。所以咱们须要对二叉树的遍历过程革新一下，这里以层序遍历为例。在遍历的过程中，为了残缺的示意二叉树，思考将叶节点下的 null 也记录。上面咱们来看一下具体的实现。

序列化

咱们能够借助队列来实现二叉树的层序遍历，在层序遍历的过程中，咱们把越过叶子节点的 null 也退出序列化的后果中。具体算法流程如下所示：

  1. 如果给定的二叉树为空，间接返回 ”[]”
  2. 初始化一个队列 queue，并把根节点退出。

  3. 对二叉树进行层序遍历。当队列为空时跳出。

    • 节点出队，记为 node。
    • 如果 node 不为空，将 node.val 退出后果列表中，并且将 node 的左、右子节点入队。如果 node 为空，将“null”退出后果列表中。
  4. 拼接后果列表，用 ',' 隔开，首尾增加中括号；并将其返回。

反序列化

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

  1. 如果 data 为空，间接返回 null。
  2. 初始化列表 vals（去掉首尾括号，再用逗号隔开），指针 i = 1，将根节点 root（值为 vals[0]）入队；

  3. 按层构建二叉树，当队列为空时跳出；

    • 节点出队，记为 node。
    • 构建 node 的左子节点，node.left 的值为 vals[i]，并将 node.left 入队；而后执行 i =i+1。
    • 构建 node 的右子节点，node.right 的值为 vals[i]，并将 node.right 入队；而后执行 i =i+1。
  4. 返回根节点 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
退出移动版