二叉树题目:二叉树的序列化与反序列化

这篇具有很好参考价值的文章主要介绍了二叉树题目:二叉树的序列化与反序列化。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

标题和出处

标题:二叉树的序列化与反序列化

出处:297. 二叉树的序列化与反序列化

难度

8 级

题目描述

要求

序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。

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

示例

示例 1:

二叉树题目:二叉树的序列化与反序列化,数据结构和算法,# 树,树,二叉树

输入: root   =   [1,2,3,null,null,4,5] \texttt{root = [1,2,3,null,null,4,5]} root = [1,2,3,null,null,4,5]
输出: [1,2,3,null,null,4,5] \texttt{[1,2,3,null,null,4,5]} [1,2,3,null,null,4,5]

示例 2:

输入: root   =   [] \texttt{root = []} root = []
输出: [] \texttt{[]} []

数据范围

  • 树中结点数目在范围 [0,   10 4 ] \texttt{[0, 10}^\texttt{4}\texttt{]} [0, 104]
  • -1000 ≤ Node.val ≤ 1000 \texttt{-1000} \le \texttt{Node.val} \le \texttt{1000} -1000Node.val1000

前言

这道题要求实现二叉树的序列化与反序列化,将二叉树序列化为一个字符串之后可以将字符串反序列化得到原始二叉树。为了能反序列化得到原始二叉树,两个不同的二叉树的序列化结果一定不同。

二叉树的序列化可以使用深度优先搜索或广度优先搜索实现,反序列化的执行逻辑由序列化的执行逻辑决定。

解法一

思路和算法

使用深度优先搜索实现二叉树的序列化时,可以存储二叉树的前序遍历的结果,包括空结点,即如果一个非空结点的某个子结点为空,则空的子结点也需要包含在序列化的结果中。序列化的结果中,非空结点使用结点值表示,空结点使用字符 ‘#’ \text{`\#'} ‘#’ 表示,每个结点之间使用逗号分隔。该序列化的方法可以确保两个不同的二叉树的序列化结果一定不同。

例如,示例 1 的二叉树的序列化结果是 “1,2,#,#,3,4,#,#,5,#,#" \text{``1,2,\#,\#,3,4,\#,\#,5,\#,\#"} “1,2,#,#,3,4,#,#,5,#,#"

反序列化时,首先将序列化结果根据逗号分隔成字符串数组,然后遍历数组并构造二叉树。构造二叉树的过程需要模拟二叉树的前序遍历的过程,使用栈存储尚未填充左右子结点的结点。

数组的首个元素为根结点值,根据数组的首个元素创建根结点,将根结点入栈。遍历数组中的其余元素,对于每个元素,执行如下操作。

  1. 如果当前元素是 ‘#’ \text{`\#'} ‘#’,则创建空结点,否则根据当前元素创建非空结点。

  2. 栈顶结点为当前结点的父结点,判断当前结点作为父结点的左子结点还是右子结点。

    • 如果父结点的左子结点为空且不为 ‘#’ \text{`\#'} ‘#’,则将当前结点作为父结点的左子结点。

    • 否则,将当前结点作为父结点的右子结点,并将父结点出栈。

  3. 如果当前结点不为空,则将当前结点入栈。

遍历结束之后,即可得到原始二叉树,返回根结点。

代码

public class Codec {
    public String serialize(TreeNode root) {
        if (root == null) {
            return "#";
        }
        StringBuffer sb = new StringBuffer();
        sb.append(root.val);
        sb.append(',');
        sb.append(serialize(root.left));
        sb.append(',');
        sb.append(serialize(root.right));
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        if ("#".equals(data)) {
            return null;
        }
        String[] arr = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        stack.push(root);
        boolean isLeftNull = false;
        int length = arr.length;
        for (int i = 1; i < length; i++) {
            String str = arr[i];
            TreeNode parent = stack.peek();
            TreeNode node = "#".equals(str) ? null : new TreeNode(Integer.parseInt(str));
            if (parent.left == null && !isLeftNull) {
                parent.left = node;
                if (node == null) {
                    isLeftNull = true;
                }
            } else {
                parent.right = node;
                stack.pop();
                isLeftNull = false;
            }
            if (node != null) {
                stack.push(node);
            }
        }
        return root;
    }
}

复杂度分析

  • 时间复杂度:序列化和反序列化的时间复杂度都是 O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。序列化和反序列化的过程中,每个结点都被访问一次。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。空间复杂度包括栈空间和将字符串转化成的数组。

解法二

思路和算法

使用广度优先搜索实现二叉树的序列化时,可以存储二叉树的层序遍历的结果,包括空结点,即如果一个非空结点的某个子结点为空,则空的子结点也需要包含在序列化的结果中。序列化的结果中,非空结点使用结点值表示,空结点使用字符 ‘#’ \text{`\#'} ‘#’ 表示,每个结点之间使用逗号分隔。该序列化的方法可以确保两个不同的二叉树的序列化结果一定不同。

例如,示例 1 的二叉树的序列化结果是 “1,2,3,#,#,4,5,#,#,#,#" \text{``1,2,3,\#,\#,4,5,\#,\#,\#,\#"} “1,2,3,#,#,4,5,#,#,#,#"

反序列化时,首先将序列化结果根据逗号分隔成字符串数组,然后遍历数组并构造二叉树。构造二叉树的过程需要模拟二叉树的层序遍历的过程,使用队列存储尚未填充左右子结点的结点。

数组的首个元素为根结点值,根据数组的首个元素创建根结点,将根结点入队列。遍历数组中的其余元素,对于每个元素,执行如下操作。

  1. 如果当前元素是 ‘#’ \text{`\#'} ‘#’,则创建空结点,否则根据当前元素创建非空结点。

  2. 队首结点为当前结点的父结点,判断当前结点作为父结点的左子结点还是右子结点。

    • 如果父结点的左子结点为空且不为 ‘#’ \text{`\#'} ‘#’,则将当前结点作为父结点的左子结点。

    • 否则,将当前结点作为父结点的右子结点,并将父结点出队列。

  3. 如果当前结点不为空,则将当前结点入队列。

遍历结束之后,即可得到原始二叉树,返回根结点。

代码

public class Codec {
    public String serialize(TreeNode root) {
        if (root == null) {
            return "#";
        }
        StringBuffer sb = new StringBuffer();
        sb.append(root.val);
        sb.append(',');
        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode left = node.left, right = node.right;
            if (left == null) {
                sb.append('#');
            } else {
                sb.append(left.val);
                queue.offer(left);
            }
            sb.append(',');
            if (right == null) {
                sb.append('#');
            } else {
                sb.append(right.val);
                queue.offer(right);
            }
            sb.append(',');
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        if ("#".equals(data)) {
            return null;
        }
        String[] arr = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);
        boolean isLeftNull = false;
        int length = arr.length;
        for (int i = 1; i < length; i++) {
            String str = arr[i];
            TreeNode parent = queue.peek();
            TreeNode node = "#".equals(str) ? null : new TreeNode(Integer.parseInt(str));
            if (parent.left == null && !isLeftNull) {
                parent.left = node;
                if (node == null) {
                    isLeftNull = true;
                }
            } else {
                parent.right = node;
                queue.poll();
                isLeftNull = false;
            }
            if (node != null) {
                queue.offer(node);
            }
        }
        return root;
    }
}

复杂度分析

  • 时间复杂度:序列化和反序列化的时间复杂度都是 O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。序列化和反序列化的过程中,每个结点都被访问一次。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。空间复杂度包括队列空间和将字符串转化成的数组。文章来源地址https://www.toymoban.com/news/detail-817721.html

到了这里,关于二叉树题目:二叉树的序列化与反序列化的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 想要精通算法和SQL的成长之路 - 二叉树的序列化和反序列化问题

    想要精通算法和SQL的成长之路 - 系列导航 二叉树的层序遍历 像这种从上至下并且按层打印的,可以称之为 二叉树的广度优先搜索( BFS ) 。而这类算法往往借助 队列的一个先入先出特性 来实现。 那么有这么几个步骤: 1.特殊处理还有初始化动作。 2. BFS 循环: 最终完整代

    2024年02月07日
    浏览(47)
  • 刷题日记01:序列化和反序列化二叉树

    一.概念理解: 题目如下:https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/ 何为序列化? 序列化我们可以理解为层序遍历的结果,即将所有的结点的信息,按照层序遍历的结果拼接到一个字符串中,但是与一般的层序遍历有所不同的是:序列化要输出所有的结点信息,而层序遍历

    2024年02月13日
    浏览(53)
  • 【序列化与反序列化】关于序列化与反序列化MessagePack的实践

    在进行序列化操作之前,我们还对系统进行压测,通过 jvisualvm 分析cpu,线程,垃圾回收情况等;运用火焰图 async-profiler 分析系统性能,找出程序中占用CPU资源时间最长的代码块。 代码放置GitHub:https://github.com/nateshao/leetcode/tree/main/source-code/src/main/java/com/nateshao/source/code/ser

    2024年02月11日
    浏览(55)
  • 【Linux】序列化与反序列化

    目录 前言 什么是应用层? 再谈\\\"协议\\\"  什么是序列化和反序列化 网络版计算器 整体流程实现 Sock.hpp的实现 TcpServer.hpp的实现 Protocol.hpp的实现 CalServer.cc的编写 CalClient.cc的编写 整体代码           本章是属于TCP/UDP四层模型中的第一层 应用层 相关的内容。主要介绍了序列

    2024年02月10日
    浏览(39)
  • Flutter笔记:序列化与反序列化

    Flutter笔记 序列化与反序列化 作者 : 李俊才 (jcLee95):https://blog.csdn.net/qq_28550263 邮箱 : 291148484@163.com 本文地址 :https://blog.csdn.net/qq_28550263/article/details/133340592 序列化是一种将复杂数据结构(例如对象、数组、字典等)转换为线性格式或字节流的过程,以便于数据的存储

    2024年02月07日
    浏览(55)
  • 序列化与反序列化读取配置文件

    定义一个连接配置文件类OmCipNetParam 定义一个结构体,传递函数运行结果和运行信息 ​ 使用Newtonsoft.Json进行序列化和反序列化读写配置文件 同理反序列读取配置文件 注意这里需要引入库

    2024年02月08日
    浏览(56)
  • 4.4. 对象序列化与反序列化

    在本节中,我们将详细讨论Java中的对象序列化与反序列化概念、使用方法以及实例。对象序列化是将对象的状态信息转换为字节流的过程,而反序列化则相反,是将字节流恢复为对象的过程。 4.4.1 为什么需要对象序列化? 对象序列化的主要目的是为了在不同的系统间传输对

    2024年02月07日
    浏览(54)
  • 【计算机网络】序列化与反序列化

    通过打包的方式,将结构体message发送给对方 对方收到后就会报告给上层QQ客户端 结构化的数据 是由 多个 string 构成的 而以前在网络套接字 发送时,都是按照一个字符串的方式来发送和接收的 所以想办法 ,把多个字符串 转化为 一个大\\\"字符串\\\",对方在接收时也是一个长的

    2024年02月10日
    浏览(42)
  • Springboot Jackson 序列化与反序列化配置

    可解决在使用默认反序列化Jackson时,LocalDateTime类型的请求参数反序列化失败的问题

    2024年02月02日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包