leetcode刷题(剑指offer) 297.二叉树的序列化和反序列化

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

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

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

提示: 输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。

示例 1:

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

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

示例 4:

输入:root = [1,2]
输出:[1,2]

提示:

  • 树中结点数在范围 [0, 104]
  • -1000 <= Node.val <= 1000

题解

这道题涉及到了二叉树的序列化与反序列化,由于序列化和反序列化的操作必须是可逆的,因此必须将完整的二叉树序列化(就是将叶子节点下面的节点也都序列化出来,序列化成两个null),这样反序列化之后的树才能是唯一的。以示例一来举例。

将示例一的输入序列化之后得到的结果是这样的。

1,2,3,null,null,4,5,null,null,null,null

可以使用BFS的思想来层序遍历取出各个元素来生成这个字符串,这部分的思路类似于这题,二叉树的层序遍历。

代码实现如下:

public static String serialize(TreeNode root) {
    if (root == null) {
        return "";
    }
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    StringBuilder sb = new StringBuilder();
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node.val == NULL) {
            sb.append("null");
            sb.append(",");
            continue;
        }else {
            sb.append(node.val);
            sb.append(",");
        }
        if (node.left != null) {
            queue.add(node.left);
        }else {
            queue.add(new TreeNode(NULL));
        }
        if (node.right != null) {
            queue.add(node.right);
        }else {
            queue.add(new TreeNode(NULL));
        }
    }
    return sb.substring(0, sb.length() - 1);
}

序列化完成之后,就可以考虑反序列化的问题了,我们先将序列化之后的String按照,分割成一个String数组,这里的难点在于如何定位到当前节点的值在序列化之后的String中的位置。

感觉有点规律,但是又不知道规律在哪,可以画图,如下所示。

图中-左边的数字表示这个节点的值在序列化之后的数组中的index,右边的数字表示这个节点的值。

通过观察可以发现,每个节点的两个叶子节点的index,可以根据父节点的index计算出来,如下。

leftIndex = 2 * index + 1;
rightIndex = 2 * index + 2;

因此可以按照序列化同样的逻辑来进行反序列化,使用BFS。

代码实现如下:

package com.offer;

import com.jvm.jad.T;
import com.offer.leetcode.datastruct.TreeNode;
import com.springAnnotation.pojo.A;
import com.缺失的第一个正数;
import sun.reflect.generics.tree.Tree;

import java.util.*;

public class _297二叉树的序列化与反序列化 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        TreeNode r = root.right;
        r.left = new TreeNode(4);
        r.right = new TreeNode(5);
        System.out.println(serialize(root));
        System.out.println(deserialize(serialize(root)));
    }

    private static int NULL = -1001;


    // Encodes a tree to a single string.
    public static String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.val == NULL) {
                sb.append("null");
                sb.append(",");
                continue;
            }else {
                sb.append(node.val);
                sb.append(",");
            }
            if (node.left != null) {
                queue.add(node.left);
            }else {
                queue.add(new TreeNode(NULL));
            }
            if (node.right != null) {
                queue.add(node.right);
            }else {
                queue.add(new TreeNode(NULL));
            }
        }
        return sb.substring(0, sb.length() - 1);
    }

    // Decodes your encoded data to tree.
    public static TreeNode deserialize(String data) {
        if ("".equals(data)) {
            return null;
        }
        String[] nodeVals = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(nodeVals[0]));
        int index = 0;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            index++;
            String val = nodeVals[2 * index + 1];
            if (!"null".equals(val)) {
                node.left = new TreeNode(Integer.parseInt(val));
                queue.add(node.left);
            }
            val = nodeVals[2 * index + 2];
            if (!"null".equals(val)) {
                node.right = new TreeNode(Integer.parseInt(val));
                queue.add(node.right);
            }
        }
        return root;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/368211.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用wda框架实现IOS自动化测试详解

目录 1、weditor元素定位工具 1.1、weditor的安装和使用 2、wda iOS自动化框架 2.1、wda概述 2.2、wda安装 2.3、wda的使用 2.3.1、全局配置 2.3.2、创建客户端 2.3.3、APP相关操作 1、启动APP 2、关闭APP 3、获取APP状态信息 4、获取当前APP的运行信息 2.3.4、设…

ruoyi(若依)(el-menu也可参考)菜单栏过长显示省略号才显示气泡

一、背景 若依前后端分离的版本&#xff0c;新版本中优化了菜单名称过长悬停显示标题&#xff0c;但是是悬浮所有长度大于5的标题。可以查看提交记录&#xff1a;https://gitee.com/y_project/RuoYi-Cloud/commit/99932d91c0144da9f34f5bb05683cc0b86303217 但是我希望是只悬浮…

Vulnhub靶机:hacksudo2 (HackDudo)

一、介绍 运行环境&#xff1a;Virtualbox 攻击机&#xff1a;kali&#xff08;10.0.2.15&#xff09; 靶机&#xff1a;hacksudo2 (HackDudo)&#xff08;10.0.2.44&#xff09; 目标&#xff1a;获取靶机root权限和flag 靶机下载地址&#xff1a;https://download.vulnh…

双非本科准备秋招(15.3)—— 力扣二叉树

今天学了二叉树结点表示法&#xff0c;建树代码如下。 public class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left …

C++ | 部分和函数partial_sum的使用技巧

如果你需要处理一个数组的前缀和&#xff0c;或者数组中某一段元素的前缀和&#xff0c;你会怎么做呢&#xff1f; partial_sum函数是STL中的函数&#xff0c;用于计算范围的部分和&#xff0c;并从结果开始分配范围中的每个元素&#xff0c;range[first,last)中相应元素的部分…

MH-ET LIVE Boards(ATTiny88)实验一---点亮板载灯

MH-ET LIVE Boards(ATTiny88&#xff09;实验一点亮板载灯 在Arduino IDE中添加开发板资源包加入开发板json添加开发板 安装开发板驱动方法一&#xff1a;github下载2.0a4.rar方法二&#xff1a;开发板的package包中自带的2.0a4.rar安装驱动确认安装成功 blink.ino程序测试![在…

知识图谱嵌入学习在推理方法中的应用与挑战

目录 前言1 关系推理的嵌入模型1.1 嵌入模型介绍1.2 模型的差异1.3 嵌入模型的发展趋势 2 符号推理与向量推理3 嵌入模型的多样性4 强化学习与挑战5 元关系学习结论 前言 在人工智能领域&#xff0c;推理一直是关键任务之一。然而&#xff0c;传统的符号推理受限于人工定义&am…

【Vitis】Vitis HLS学习系列笔记 :第一个例程

在学习vitis的过程中一定要跑几个例程试试看&#xff0c;这中间遇到了几个小问题&#xff0c;记录下 有干货&#xff0c;请注意查收&#xff1a;作为新手&#xff0c;跑例程大概率会遇到问题&#xff0c;这里记录几个问题&#xff0c;如果刚好你也遇到&#xff0c;一定会帮到你…

每日一题——LeetCode1389.按既定顺序创建目标数组

方法一 splice 使用splice函数就可以在数组的指定索引位置添加元素 var createTargetArray function(nums, index) {let res[]for(let i0;i<nums.length;i){res.splice(index[i],0,nums[i])}return res }; 消耗时间和内存情况&#xff1a; 方法二 模拟 如果res[index[…

计算机网络——链路层(1)

计算机网络——链路层&#xff08;1&#xff09; 小程一言专栏链接: [link](http://t.csdnimg.cn/ZUTXU)前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家&#xff0c; [跳转到网站](https://www.captainbed.…

[每日一题] 02.03 - 质因数分解

质因数分解 枚举到n的平方根&#xff08;得包括平方根&#xff09; 偶数去除 import math n int(input()) if n % 2 0:print(max(n // 2,2)) else:for i in range(3,int(math.sqrt(n)) 1,2):if n % i 0:print(max(n // i,i))

2023年度总结 | 关于意义,爱与回望——写给清醒又无知的20岁

Hi&#xff0c;大家好&#xff0c;我是半亩花海&#xff0c;一名再普通不过的大学生。2023年&#xff0c;20岁&#xff0c;充实而零乱的一年&#xff0c;清醒又无知的一年。年末&#xff0c;最近的一些事儿也让我逐渐地有感而发&#xff0c;心静&#xff0c;除杂&#xff0c;思…

redis布隆过滤器(Bloom)详细使用教程

文章目录 布隆过滤器1. 原理2. 结构和操作3. 特点和应用场景4. 缺点和注意事项 应用-redis插件布隆过滤器使用详细过程安装以及配置springboot项目使用redis布隆过滤器下面是布隆过滤器的一些基础命令 扩展 布隆过滤器 Bloom 过滤器是一种概率型数据结构&#xff0c;用于快速判…

在低代码平台上实现精益软件开发:提高效率与灵活性的关键实践

什么是精益软件开发&#xff1f; 精益软件开发是一种敏捷的软件开发框架。它基于最小化浪费和最大化价值的原则。该框架基于最小可行产品策略运行&#xff0c;该策略强调交付具有基本基本功能的产品&#xff0c;然后根据收到的反馈进行迭代以即兴发挥并提供卓越。 精益软件开发…

编译opencv4.6问题汇总,第三方软件包见我发的资源

win10系统 python3.8.2&#xff0c;cmake-3.15.5-win64-x64&#xff0c;opencv4.6 编译方式见&#xff1a;OpenCV的编译 - 知乎 本文主要总结问题。赠人玫瑰手留余香。 问题1 Problem with installing OpenCV using Visual Studio and CMake (error code: MSB3073) 解决方法…

魔改冰蝎 —— 绕过检测,自动生成免杀后门

为什么要魔改工具&#xff1f; 生成的代码很容易被监测 生成的后门很容易被杀软杀掉 了解冰蝎流量特征 开启http代理&#xff0c;数据经过BP抓包进行分析数据 冰蝎数据包分析&#xff1a; 1、三个请求头固定 AcceptAccept-LanguageUser-Agent&#xff08;内部有十个&a…

VSCODE使用ssh远程连接时启动服务器失败问题

错误情况 ping服务器的ip可通并且使用terminal可以ssh连接到远程服务器。但使用vscode的remote-ssh时&#xff0c;在「输出」栏出现了一直报 Waiting for server log… 的情况&#xff01; 解决方法一 重置服务器设置&#xff0c;包括以下手段&#xff1a; 1.清理服务器端的…

问题:测风站应设置在平直的巷道中,其前后()范围内不得有障碍物和拐弯等局部阻力。 #微信#媒体

问题&#xff1a;测风站应设置在平直的巷道中&#xff0c;其前后&#xff08;&#xff09;范围内不得有障碍物和拐弯等局部阻力。 参考答案如图所示

windows安装配置anaconda 创建并激活自己的虚拟环境(亲测可行,装不好你打我)

一.下载 选择一&#xff1a;进入清华镜像选择过去的版本 https://mirrors.tuna.tsinghua.edu.cn/anaconda/archive/ 本人电脑配置不高&#xff0c;并且一般过去的版本比较稳定&#xff0c;因此保守起见选择2022年5月的版本。 选择二&#xff1a;进入官网&#xff0c;下载最…

备战蓝桥杯---搜索(应用基础1)

话不多说&#xff0c;直接看题&#xff1a; 显然&#xff0c;我们直接用深搜&#xff0c;我们可以先把空位用结构体存&#xff0c;然后打表存小方块&#xff0c;再用数组存行列。 下面是AC代码&#xff1a; #include<bits/stdc.h> using namespace std; int a[12][12];…