刷题日记01:序列化和反序列化二叉树

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

一.概念理解:

题目如下:https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/

何为序列化?

序列化我们可以理解为层序遍历的结果,即将所有的结点的信息,按照层序遍历的结果拼接到一个字符串中,但是与一般的层序遍历有所不同的是:序列化要输出所有的结点信息,而层序遍历一般不会对null结点进行输出。如下:

刷题日记01:序列化和反序列化二叉树,算法,数据结构,Powered by 金山文档

二.解决思路:

1.序列化:

既然与层序遍历存在相同之处,那么解决思路同样存在相同之处了:

我们解决层序遍历的题目时,一般利用辅助队列空间,即创建一个存放结点的LinkedList,判断当前结点是否非空,不为空则加入到队列中,同时设置一个计数器:不断记录当前队列中存在几个元素,后面输出,力扣题目以及代码如下:

https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<>(){{ add(root); }};
        ArrayList<Integer> ans = new ArrayList<>();
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        int[] res = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++)
            res[i] = ans.get(i);
        return res;
    }
}

作者:jyd
链接:https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/solution/mian-shi-ti-32-i-cong-shang-dao-xia-da-yin-er-ch-4/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

序列化不需要设置计数器,但是遍历的思路和其完全相同,但是序列化需要利用StringBuilder进行字符串的拼接,就是将每次放入队列的元素拼接到StringBuilder中,null也需要拼接,通过判断队列是否为空,进行不断的循环:

public String serialize(TreeNode root) {
        //检验头结点的合法性
        if(root == null) return "[]";
        //拼接左括号
        StringBuilder res = new StringBuilder("[");
        //将头结点接入
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            //由于null也需要加入队列,所以这时需判断加入队列的元素是否为null
            if(node != null) {
                //  将当前结点进行拼接
                res.append(node.val + ",");
                //
                queue.add(node.left);
                queue.add(node.right);
            }
            //如果是null直接在StringBuilder中拼接null
            else res.append("null,");
        }
        //将最后一个逗号删除
        res.deleteCharAt(res.length() - 1);
        //拼接右半部分括号
        res.append("]");
        return res.toString();

2.反序列化

反序列化可以理解为序列化的逆过程:在序列化字符串中按照下标不断取出新的元素,并判断是否为空,不是空则加入到辅助队列中,不断循环直至队列中的元素为空:循环结束。

具体实现逻辑的代码如下:文章来源地址https://www.toymoban.com/news/detail-540932.html

 public TreeNode deserialize(String data) {
        //如果序列化字符串中的元素为空,直接返回null
        if(data.equals("[]")) return null;
         //转化为字符串数组,便于节点的遍历
        String[] vals = data.substring(1, data.length() - 1).split(",");
        //先将第一个元素加入队列
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        int i = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            //以队列是否为空为不断循环的条件
            if(!vals[i].equals("null")) {
                //当前不为空则加入到队列,并将其作为当前元素的左子节点
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.left);
            }
            i++;
            if(!vals[i].equals("null")) {
            //当前不为空则加入到队列,并将其作为当前元素的右子节点
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.right);
            }
            i++;
        }
        //反序列化结束,返回根节点
        return root;
    }

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

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

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

相关文章

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

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

    2024年01月23日
    浏览(43)
  • Leetcode 297. 二叉树的序列化与反序列化

    297. 二叉树的序列化与反序列化

    2024年02月07日
    浏览(40)
  • 【LeetCode力扣】297. 二叉树的序列化与反序列化

      目录 1、题目介绍 2、解题思路  2.1、详细过程图解 2.2、代码描述   2.3、完整代码   原题链接:297. 二叉树的序列化与反序列化 - 力扣(LeetCode)   示例 1: 输入: root = [1,2,3,null,null,4,5] 输出: [1,2,3,null,null,4,5] 示例 2: 输入: root = [ ] 输出: [ ] 示例 3: 输入: root = [1

    2024年02月08日
    浏览(64)
  • 二叉树的序列化(serialization)与反序列化(de-serialization)

    目录 1. 概要 2. 二叉树的序列化 2.1 基于前序遍历的序列化 2.2 基于后序遍历的序列化 2.3 基于层序遍历的序列化 3. python实现 3.1 二叉树节点的表示 3.2 层序遍历序列化的python实现 3.3 层序遍历反序列化的python实现 3.4 测试          本文简要介绍二叉树的序列化处理和反序列

    2024年02月06日
    浏览(38)
  • Unity-序列化和反序列化

    序列化是指把对象转换为字节序列的过程,而反序列化是指把字节序列恢复为对象的过程。序列化最主要的用途就是传递对象和保存对象。 在Unity中保存和加载、prefab、scene、Inspector窗口、实例化预制体等都使用了序列化与反序列化。 1 自定义的具有Serializable特性的非抽象、

    2024年01月24日
    浏览(57)
  • 【Linux】序列化和反序列化

    在网络编程中,直接使用 结构体 进行数据传输会出错,因为 本质上socket无法传输结构体 ,我们只有将结构体装换为字节数组,或者是字符串格式来传输,然后对端主机收到了数据,再将其转化为结构体,这就是序列化和反序列化的过程! 序列化 (Serialization)是将对象的状态

    2024年02月10日
    浏览(42)
  • Java序列化和反序列化

    目录 一、序列化和反序列化 二、Java序列化演示 三、反序列化漏洞 1、含义 ​序列化就是内存中的对象写入到IO流中,保存的格式可以是二进制或者文本内容。反序列化就是IO流还原成对象。 2、用途 (1)传输网络对象 (2)保存Session 1、序列化 java.io.ObjectOutputStream代表对象

    2023年04月25日
    浏览(39)
  • 什么是序列化和反序列化?

    JSON(JavaScript Object Notation)和XML(eXtensible Markup Language)是两种常用的数据交换格式,用于在不同系统之间传输和存储数据。 JSON是一种轻量级的数据交换格式,它使用易于理解的键值对的形式表示数据。JSON数据结构简单明了,易于读写和解析,是基于JavaScript的一种常用数据

    2024年02月09日
    浏览(57)
  • Java序列化和反序列化机制

    在阅读 ArrayList 源码的时候,注意到,其内部的成员变量动态数组 elementData 被Java中的 transient 修饰 transient 意味着Java在序列化时会跳过该字段(不序列化该字段) 而Java在默认情况下会序列化类(实现了 Java.io.Serializable 接口的类)的所有非瞬态(未被 transient 修饰

    2024年03月15日
    浏览(50)
  • TCP定制协议,序列化和反序列化

    目录 前言 1.理解协议 2.网络版本计算器 2.1设计思路 2.2接口设计 2.3代码实现: 2.4编译测试 总结         在之前的文章中,我们说TCP是面向字节流的,但是可能对于面向字节流这个概念,其实并不理解的,今天我们要介绍的是如何理解TCP是面向字节流的,通过编码的方式,自

    2024年02月12日
    浏览(34)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包