【每日一题Day316】LC449序列化和反序列化二叉搜索树 | BFS

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

序列化和反序列化二叉搜索树【LC449】

序列化是将数据结构或对象转换为一系列位的过程,以便它可以存储在文件或内存缓冲区中,或通过网络连接链路传输,以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串,并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

BFS
  • 思路

    • 序列化:按照层序遍历序列化二叉搜索树,每个值以","分隔,不记录null值
    • 反序列化:由于该树为二叉搜索树,满足左子树值小于根、右子树值大于根;因此对于每个节点 i i i,可以从根出发,找到相应的插入位置,将当前节点记为cur,插入节点值记为 x x x
      • 如果当前节点的左子节点为空,并且 c u r . v a l > x cur.val > x cur.val>x,那么插入位置为 c u r . l e f t cur.left cur.left
      • 如果当前节点的右子节点为空,并且 c u r . v a l < x cur.val < x cur.val<x,那么插入位置为 c u r . r i g h t cur.right cur.right
      • 都不满足时,选择向左或者向右遍历
  • 实现文章来源地址https://www.toymoban.com/news/detail-694398.html

    //@背书包的小白熊
    public class Codec {
    
        // Encodes a tree to a single string.
        //java广度优先搜索层序遍历,记录所有节点的val值,用逗号隔开
        public String serialize(TreeNode root) {
            if (root == null) return "";
            Queue<TreeNode> queue = new LinkedList();
            queue.offer(root);
            StringBuilder sb = new StringBuilder();
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                sb.append(cur.val).append(",");
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
            return sb.deleteCharAt(sb.length() - 1).toString();
        }
    
        // Decodes your encoded data to tree.
        //将字符串恢复成树
        public TreeNode deserialize(String data) {
            if (data.equals("")) return null;
            //将data分隔开
            String[] arr = data.split(",");
            //初始化根节点
            TreeNode root = new TreeNode(Integer.valueOf(arr[0]));
            //从第二个节点开始循环,二叉搜索树的特点是:
            //1.非空左子树的所有键值小于其根结点的键值。
            //2.非空右子树的所有键值大于其根结点的键值。
            //3.左、右子树都是二叉搜索树。
            //利用此性质,每次搜索插入节点时间复杂度为O(logn),总体时间复杂度为O(nlogn)
            for (int i = 1; i < arr.length; i++) {
                int x = Integer.valueOf(arr[i]);
                TreeNode cur = root;
                while (cur != null) {   
                    //如果左子树为空,并且x < cur.val 证明此节点就是需要插入的节点位置
                    if (cur.left == null && x < cur.val) {
                        cur.left = new TreeNode(x);
                        break;
                        //如果右子树为空,并且x > cur.val 证明此节点就是需要插入的节点位置
                    } else if (cur.right == null && x > cur.val) {
                        cur.right = new TreeNode(x);
                        break;
                    }              
                    //选择向左或向右遍历
                    if (x < cur.val) cur = cur.left;
                    else cur = cur.right;
                }
            }
            return root;
        }
    }
    
    • 复杂度
      • 时间复杂度: O ( n ) O(n) O(n)
      • 空间复杂度: O ( n log ⁡ n ) O(n \log n) O(nlogn)

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

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

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

相关文章

  • Unity-序列化和反序列化

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

    2024年01月24日
    浏览(54)
  • 什么是序列化和反序列化?

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

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

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

    2024年03月15日
    浏览(47)
  • Java中序列化和反序列化解释

    在Java中,序列化(Serialization)是指将对象的状态转换为字节流的过程,以便将其保存到文件、在网络中传输或持久化到数据库中。而反序列化(Deserialization)则是将字节流转换回对象的过程,恢复对象的状态。 序列化和反序列化主要用于以下场景: 1. 对象持久化:通过序列

    2024年02月07日
    浏览(54)
  • jackjson自定义序列化和反序列化

    JRT引用的jackjson作为json处理库。由于JRT.ORM要求表不用datetime类型,把日期和时间用Int存储,所以ORM要支持日期时间的转换。为什么要把日期时间不用datetime而用Int,比如日期:20240117,时间就是从0点到当前的秒数。因为不用datetime兼容性好,不会因为不同库datetime函数不同而要

    2024年01月18日
    浏览(36)
  • [计算机网络]---序列化和反序列化

    前言 作者 :小蜗牛向前冲 名言 :我可以接受失败,但我不能接受放弃    如果觉的博主的文章还不错的话,还请 点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正  目录  一、再谈协议 二、序列化和反序化 1、网络版本计算器的场景搭建 2、

    2024年02月20日
    浏览(42)
  • TCP定制协议,序列化和反序列化

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

    2024年02月12日
    浏览(33)
  • java中的序列化和反序列化

    objectOutputStream 对象的序列化,以流的形式将对象写入文件 构造方法: objectOutputStream(OutputStream out) 传入一个字节输入流创建objectOutputStream对象 成员方法: void writeObject(object obj) 将指定的对象写入objectOutputStream 使用步骤: 创建一个类,这个类实现Serializable接口,Serializable是一

    2024年02月14日
    浏览(33)
  • iOS处理json,序列化和反序列化

    Mantle 是一个开源的 Objective-C 框架,用于在 iOS 和 macOS 应用程序中实现模型层的序列化和反序列化。它提供了一种简单而强大的方式来将 JSON数据格式转换为自定义的数据模型对象,以及将数据模型对象转换为字典或 JSON 格式。 Mantle具有如下特点 自动映射 Mantle自动将 JSON 数据

    2024年02月11日
    浏览(60)
  • 从浅入深理解序列化和反序列化

    什么是java序列化 序列化:把对象转换为字节序列的过程 反序列:把字节序列恢复为对象的过程 对象序列化机制(object serialization)是java语言内建的一种对象持久化方式,通过对象序列化,可以将对象的状态信息保存为字节数组,并且可以在有需要的时候将这个字节数组通过

    2024年02月06日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包