序列化二叉树

2021年11月26日 阅读数:2
这篇文章主要向大家介绍序列化二叉树,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

序列化二叉树

问题描述

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

示例:算法

输入:root = [1,2,3,null,null,4,5]app

输出:[1,2,3,null,null,4,5]函数

分析问题

咱们都知道对于不一样的二叉树进行先序、中序、后序或者层序遍历获得的遍历结果有多是相同的,即若是知道了遍历序列,咱们不能肯定惟一的一颗二叉树,而题目要求的序列化和反序列化是一对可逆操做,即对一棵树进行序列化后,咱们还能经过序列化后的结果反序列化还原成原来的那棵树。因此咱们须要对二叉树的遍历过程改造一下,这里以层序遍历为例。在遍历的过程当中,为了完整的表示二叉树,考虑将叶节点下的 null 也记录。下面咱们来看一下具体的实现。设计

序列化

咱们能够借助队列来实现二叉树的层序遍历,在层序遍历的过程当中,咱们把越过叶子节点的null也加入序列化的结果中。具体算法流程以下所示:指针

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

image-20211109144508060

image-20211109144532395

image-20211109144606614

反序列化

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

  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 便可。

image-20211109150836431

image-20211109150920184

image-20211109151024749

image-20211109151046647

下面咱们来看一下代码的实现。队列

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