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

前言

二叉树的序列化是指将二叉树转化成一个字符串,便于存储或者通过网络传输。反序列化就是将字符串通过相同的规则转化成二叉树。

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

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

序列化

通过先序遍历存储每个节点,和普通的先序遍历不同的是,需要存储空节点。
序列化的结果如下:

"1,2,#,4,#,#,3,#,#,"

反序列化

一般情况下,不能只通过先序遍历构造出二叉树,而需要先序遍历和中序遍历才能构造二叉树。但是这里情况不一样,因为字符串中包含了空节点,所以可以只通过先序遍历构造出二叉树。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    String SEP = ",";
    String NULL = "#";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        traverse(root, sb);
        return sb.toString();
    }

    void traverse(TreeNode root, StringBuilder sb){
        if(root == null){
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(root.val).append(SEP);
        traverse(root.left, sb);
        traverse(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        LinkedList<String> node = new LinkedList<>();
        for(String str : data.split(SEP)){
            node.add(str);
        }
        return build(node);
    }

    TreeNode build(LinkedList<String> node){
        if(node.isEmpty()){
            return null;
        }
        String rootVal = node.removeFirst();
        if(rootVal.equals(NULL)){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(rootVal));

        root.left = build(node);
        root.right = build(node);

        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
本文转载于网络 如有侵权请联系删除

相关文章

  • wireshark 过滤方式「建议收藏」

    大家好,又见面了,我是你们的朋友全栈君。(1)协议过滤比较简单,直接在抓包过滤框中直接输入协议名即可。tcp,只显示TCP协议的数据包列表http,只查看HTTP协议的数据包列表icmp,只显示ICMP协议的数据包列表(2)IP过滤host192.168.1.104srchost192.168.1.104dsthost192.168.1.104(3)端口过滤port80srcport80dstport80(4)逻辑运算符&&与、||或、!非srchost192.168.1.104&&dstport80抓取主机地址为192.168.1.80、目的端口为80的数据包host192.168.1.104||host192.168.1.102抓取主机为192.168.1.104或者192.168.1.102的数据包!broadcast不抓取广播数据包2、显示过滤器语法和实例(1)比较操作符比较操作符有==等于、!=不等于、>大于、<小于、>=大于等于、<=小于等于。(2)协议过滤比较简单,直接在Filter框中直接输入协议名即可。注意:协议

  • IFRAME

       <iframe src="health.jsp" frameborder="0" width="1000" scrolling="no" height="100%"  id="myframe"></iframe>            <script type="text/javascript">             function reinitIframe()             {             var iframe = document.getElementById("myframe");             try{             var bHeight = iframe.contentWindow.document.body.scrollHeight;             var dHeight = iframe.contentWindow

  • idea+git合并分支解决冲突及详解步骤

    Git分支详解参考: https://blog.csdn.net/su1573/article/details/919885231、切换分支1)在idea页面右下角点击分支名2)在git分支选择框中选择项目一步步选择需要的分支这里先演示切换到master主干分支,点击Checkout切换 3)切换master主干分支成功2、合并分支1)master合并bug001分支2.1.1.拉取分支步骤:在项目上右键,Git->Repository->Pull 2)develop合并master分支2.2.1切换develop分支,原则上develop分支的代码必须和master主干保持一致 3)Hebei合并develop分支2.3.1.切换Hebei分支 切换成功 2.3.2更新本分支代码,拉取分支步骤:在项目名上右键,Git->Repository->Pull,参考2.1.12.3.3合并develop分支代码到当前分支hebei;Git->Repository->Pull 2.3.4.更新时出现冲突文件(20200604更新,内容是最新的,和上面dev

  • smartbrute - AD域的密码喷射和暴力破解工具

    此工具可用于暴力破解/喷洒ActiveDirectory帐户凭据。支持以下攻击,每种攻击都有自己的好处:NTLMoverSMBbruteforce:当找到有效帐户时,将测试它们的本地管理权限。NTLMoverLDAP暴力破解Kerberospre-authenticationbruteforce:这是最快和最隐蔽的方式。可以选择传输协议:UDP或TCP。UDP是最快的,但有时会引发错误。可以选择etype:RC4、AES128、AES256。RC4是最快的,但AES128和AES256是最隐蔽的。密码并不是唯一可以使用此工具进行暴力破解的秘密。在NTLM上进行暴力破解时:可以尝试使用NT哈希。在Kerberos上进行暴力破解时:可以尝试使用RC4密钥(即NT哈希)。找到有效帐户时:它们可以在Neo4j数据库中设置为拥有(由BloodHound使用)使用neo4j时,将突出显示在域管理员路径上的自有用户此工具可用于不同场景的两种不同模式:smart或bruteSmartmode此模式可用于通过以下方式确保在暴力破解时不锁定任何帐户:从ActiveDirectory获取启用的用户获取每个用

  • SAP CRM IBASE 一致性检查工具

    源代码:REPORTZIBASE_CONSISTENCY_CHECK. DATA:lt_ibintypeSTANDARDTABLEOFibin-in_guid, lv_guidLIKEibin-in_guid, lv_okTYPEabap_bool, lt_ibintxtypeSTANDARDTABLEOFibintx-in_guid. selectin_guidINTOTABLElt_ibinFROMibin. selectin_guidINTOTABLElt_ibintxFROMibintx. SORTlt_ibin. lv_ok=abap_true. LOOPATlt_ibintxINTOlv_guid. READTABLElt_ibinWITHKEYtable_line=lv_guidTRANSPORTINGNOFIELDS. IFsy-subrc=0. WRITE:/'Inconsistententrydetected:',lv_guidCOLORCOL_NEGATIVE. lv_ok=abap_false. ENDIF. ENDLOOP. WRI

  • Mysql 5.6 “隐式转换”导致的索引失效和数据不准确

    背景在一次进行SQl查询时,我试着对where条件中vachar类型的字段去掉单引号查询,这个时候发现这条本应该很快的语句竟然很慢。这个varchar字段有一个复合索引。其中的总条数有58989,甚至不加单引号查出来的数据不是我们想要的数据。使用的是mysql5.6版本,innoDB引擎实际情况如下下面我们来看一下执行的结果 在上面的描述中我们还得注意就是,你的where条件的字符串不加单引号必须是全数字。不然就会报错 还有可能查出来的数据不是我们想要的数据。如下图 分析从执行结果来看,使用了单引号的走了对应的索引。没有使用单引号的没有走索引,进行了全表扫描。为什么会这样呢?mysql的优化器怎么不直接进行类型转换呢?在SQL语句中单引号的引入也就是代表这个类型是字符串数据类型CHAR,VARCHAR,BINARY,VARBINARY,BLOB,TEXT,ENUM,和SET。。不加单引号也就代表这是一个字符串之外的类型,如int,bigDecimal类型等如果给一串有字幕和特殊符号的字符串不加单引号,后果就是类型转换失败导致SQl不能执行。如上图所述:1054-Unknowncolum

  • python-postgresql建表导入csv

    众(小众)所周知,excel只能存一百万条数据,csv文件只能显示一百万条数据。。。无可避免的需要使用数据库,而我所知的开源数据库中,postgresql有个很大的特点,就是对地理数据支持度较高。无可避免的又要用python去操作,那。。。 '''pm2.5-数据库'''importpsycopg2conn=psycopg2.connect(database="postgres",user="postgres",password="1234",host="127.0.0.1",port="5432")cur=conn.cursor()cur.execute("CREATETABLEmxndata1(datatimestamp,pointvarchar,longdoubleprecision,latdoubleprecision,pm25doubleprecision,\pm10doubleprecision,so2do

  • python操作txt文件中数据教程[1]-使用python读写txt文件

    程序实现filename='./test/test.txt' contents=[] DNA_sequence=[] #打开文本并将所有内容存入contents中 withopen(filename,'r')asf: forlineinf.readlines(): contents.append(line) f.close() #对contents中的内容进行遍历 #并将需要的数据存到listDNA_sequence中 forcontentincontents:#逐行遍历 p=0# forbitincontent:#对每行进行逐字遍历 ifbit=="":#遇到空格时进行处理 DNA_sequence.append(content[0:p])#将content中的0:p字段存入新列表new中,用于写入新的.txt中 break#处理完一行以后跳出当前循环 else: p=p+1#如果bit不是空格,指针加1 #print(DNA_sequence) """ ['AAACAAGGAAC

  • 《最重要的事,只有一件》第一部分 谎言 误导并阻碍成功

    第一部分谎言误导并阻碍成功介绍恼人的“真相”让我们陷入困境的不是无知,而是看似正确的谬误论断。——马克·吐温阻止你成功的6个谎言每件事都很重要同时处理多件事有规律地生活缺乏意志力试图平衡生活的各个方面大即不佳4每件事都很重要生活中的芝麻小事永远不应阻挡你去追逐伟大的事。——约翰·沃尔夫冈·冯·歌德平等是一个谎言最重要的事,也许并不是最起眼的。——鲍勃·霍克 为无谓的事做无用功澳大利亚前总理鲍勃·霍克说:“最重要的事,也许并不是最起眼的。”。成功人士对待办事项的认识清醒到位,所以排序准确 朱兰解码理查德·科克在《80/20法则》中总结:“80/20法则认为少量的原因、投入、付出常常产生大量的结果、产出、回报。”。绝大部分所得恰恰是靠较少部分付出而获得的 极端的帕累托缩小施力范围,找出你的20%,继续在这20%里缩小范围,找出关键中的关键从20%中找出20%,再从中找出20%,直到你找到最重要的那一件事!2001年,我组织了一次公司的高层会议。当时公司发展势头大好,可是尚未引起业内顶尖人士的注意。我要求精英团队头脑风暴出100个改善现状的方法。花了整整一天,我们才列好这个百项清单。第二天一

  • 私有云架构简述之存虚拟化

    一、在私有云中,常用的存储虚拟化的方式有四种。DAS(直存)、NAS(网络存储)、FCSAN(光纤存储)、ServerSAN(分布式存储)。 二、DAS直存,主要应用于本地硬盘或超融合的环境。如虚拟机的宿主机操作系统是采用直存方式,或者对超融合环境也适用(计算服务器与存储服务器合用)。三、NAS存储,主要应用于局域网的存储。一般采用NFS协议进行局域网内存储,在私有云中一般不会采用,因为存储效率不高。但在公有云中,有弹性文件服务NAS的标准局域网内服务,可以采用。四、FC-SAN存储,在私有云中大量采用。一般采用光纤+光纤交换机进行网络通信,主要有8G、16G的网络通信能力,对于高性能io、iops要求较高的场景可以采用。但随着以太网技术的发展FC-SAN存储的优势逐渐消失。五、ServerSAN存储,在私有云中大量采用。一般采用万兆以太网进行网络通信,采用SSD、PCIE等高性能等介质后,ServerSAN的分布式存储已在私有云中成为主流。六、不同的存储方式有不同的适用场景。小规模存储100TB以下建议FCSAN,大规模存储建议ServerSAN。七、存储虚拟化讲完后,我们也在思考同

  • 膨胀卷积--Multi-scale context aggregation by dilated convolutions

    Multi-scalecontextaggregationbydilatedconvolutions ICLR2016https://arxiv.org/abs/1511.07122Code: https://github.com/fyu/dilation https://github.com/bordesf/dilation针对语义分割问题semanticsegmentation,这里使用dilatedconvolutions得到multi-scalecontext信息来提升分割效果。dilatedconvolutions:首先来看看膨胀卷积dilatedconvolutions,图(a):就是一个常规的3*3卷积,1-dilatedconvolution得到F1,F1的每个位置的receptivefield是3×3 图(b):在F1的基础上,进行一个2-dilatedconvolution,注意它的点乘位置,不是相邻的3*3,得到了F2, F2的每个位置的receptivefield是7×7 图(c):在F2的基础上,进行一个4-dilatedconvolution,得到了F3,

  • 手机侧滑导航栏

    <!DOCTYPEhtml> <html> <head> <metacharset="utf-8"/> <metaname="viewport"content="width=device-width,initial-scale=1.0,maximum-scale=1.0,minimum-scale=1.0,user-scalable=no"/> <metaname="apple-touch-fullscreen"content="yes"/> <metaname="apple-mobile-web-app-capable"content="yes"/> <metaname="apple-mobile-web-app-status-bar-style"content="black"/> <metaname=&q

  • 基于深度学习的语义计算技术

    基于深度学习的语义计算技术课件

  • pandas库的学习

    pandas 官方手册 定义:pandas是基于NumPy数组构建的,使数据预处理、清洗、分析工作变得更快更简单。pandas是专门为处理表格和混杂数据设计的,而NumPy更适合处理统一的数值数组数据。 importpandasaspd 复制 数据结构:Series|DataFrame。 Series:pd.Series(list,index=[])类似于一维数组的得对象,是由一组数据+一列索引组成。可以使用切片,运算等操作,类似于ndarray。 DataFrame:pd.DataFrame(data,columns=[],index=[])是一个表格形的数据类型。常用类型。axis=1列axis=0行 数据转换: 1:pd.DataFrame(Series)可以把Series结构变为DataFrame。 2:DataFrame.values可以把DataFrame结构变为一个numpy的ndarray。也可以通过索引或者列名获得一个Series。df['列名']或者df.列名。 pd.read_excel() pandas.read_excel(io,sheet_name=0,he

  • Codeforces Global Round 15 题解

    A-SubsequencePermutation 求出\(s\)排序后的结果\(t\),计算\(s,t\)不同的位置数即可。 B-RunningforGold 答案唯一,因为如果有两个答案,那么两者是相互矛盾的。 于是顺序扫描,维护可能的答案就行了。 C-MaximizetheIntersections 如果所有位点都是空的,那么每个位点与对面相连最优。 现在有若干初始的弦,那把剩下的\(2(n-k)\)个取出,第\(i\)个连向第\(n-k+i\)个即可。 D-ArrayDifferentiation 如果\(b\)的长度为\(n+1\)就好办了,\(b_1=0\),\(a_i=b_{i+1}\)。 长度为\(n\)​,说明存在一个“环”,边权值和为\(0\)。我们枚举一个子集\(S\),作为环的边权,并且枚举正负。如果存在\(=0\)就是成功。 复杂度\(O(3^nn)\)或\(O(3^n)\)。 E-ColorsandIntervals 考虑到\(\lceil\tfrac{n}{k-1}\rceil(k-1)\gen\),我们每次处理\(k-1\)​种颜色,进行\(\lceil\

  • 【Linux学习】VMware安装centos7版本的Linux系统出现的一些问题

    1、首先登陆系统后发现一些命令不能使用,比如:ifconfig:commandnotfind,需要安装命令. 2、sudoyuminstallnet-tools发现系统不能联网 3、解决上网问题:     ipaddr  找到网卡名字ens33    vi/etc/sysconfig/network-scripts/ifcfg-ens33  打开网络信息配置文件   点击键盘【i】键,修改如下内容信息,完成之后,点击键盘【Esc】键,输入【:wq!】,点击回车键,保存退出。   修改配置文件中的 ONBOOT=yes(ONBOOT是指明在系统启动时是否激活网卡,只有在激活状态的网卡才能去连接网络,进行网络通讯)    注意:如果修改ONBOOT时显示文件只读,按i修改后,esc退出,输入:w!sudotee%就可以了   顺便更改ip信息        IPADDR=192.168.1.2

  • Docker03 Docker基础知识、Docker实战

      1Docker基础知识   1.1什么是Docker     Docker是一个可以装应用的容器,就像杯子可以装水、书包可以装书一样;docker官网     Docker是Docker公司开发的,并开源到GitHub上;     Docker是跨平台的,支持windows、linux、Macos   1.2Docker思想     1.2.1集装箱       需要运行的程序放到一个集装箱中     1.2.2标准化       运输方式       存储方式       API接口     1.2.3隔离   1.3Docker解决了什么问题     1.3.1解决运行环境不一致问题        解决了本地可以运行但是上线就出现问题     1.3.2应用之间的隔离       当一台服务器同时运行多个应用时,有可能会因为一个应用出现问题而牵扯到其他应用的运行;docker化的应用会给每个应用进行隔离,某个应用出现问题后不会影响其他的应用     1.3.3简化应用的扩展       当需要大量扩展应用程序的部署时,利用docker可以轻松实现;例如:双十

  • 挂羊头卖狗肉蓄意欺骗读者——谭浩强《C程序设计(第四版)》中所谓的“按照C99”(二)

    挂羊头卖狗肉蓄意欺骗读者——谭浩强《C程序设计(第四版)》中所谓的“按照C99”(二) 在《谭C》p4:“本书的叙述以C99标准为依据”,下面从C89到C99的主要变化方面来看看是不是这样。 《谭C》(前言)p12: ① 数据类型介绍中,增加了C99扩充的双长整型(longlongint)、复数浮点型(floatcomplex,doublecomplex,longlongcomplex)、布尔型(bool)等,使读者有所了解。 实际上,C99不但增加了longlongint,还增加了unsignedlonglongint以及扩展整数类型;C99中压根就没有floatcomplex,doublecomplex,longlongcomplex以及bool。 《谭C》(前言)p12: ② C99要求,main函数的类型一律指定为int型,并在函数的末尾加一个返回语句“return0;”。 实际上,main函数的类型一律指定为int型是C89的要求,并且C99标准并没有要求在main()末尾必须写语句“return0;”。 《谭C》p5: C99又扩充了……布尔

  • jQuery选择器总结

    jQuery的选择器可谓之强大无比,这里简单地总结一下常用的元素查找方法   $("#myELement")   选择id值等于myElement的元素,id值不能重复在文档中只能有一个id值是myElement所以得到的是唯一的元素 $("div")          选择所有的div标签元素,返回div元素数组 $(".myClass")     选择使用myClass类的css的所有元素 $("*")            选择文档中的所有的元素,可以运用多种的选择方式进行联合选择:例如$("#myELement,div,.myclass")   层叠选择器: $("forminput")      &nb

  • C# BitArray转换成int类型的两种方式

      通过位运算解决: publicstaticintBitToIntOne(BitArraybit) { intres=0; for(inti=bit.Count-1;i>=0;i--) { res=bit[i]?res+(1<<i):res; } returnres; }复制   通过CopyToAPI函数解决: publicstaticintBitToIntTwo(BitArraybit) { int[]res=newint[1]; for(inti=0;i<bit.Count;i++) { bit.CopyTo(res,0); } returnres[0]; }复制  

  • Android客户端和服务器端数据交互

     网上有很多例子来演示Android客户端和服务器端数据如何实现交互不过这些例子大多比较繁杂,对于初学者来说这是不利的,现在介绍几种代码简单、逻辑清晰的交互例子,本篇博客介绍第四种:     一、服务器端:     代码1:添加名为“AndroidServerServlet.Java”的文件 [java] viewplain copy  package com.ghj.packageofservlet;      import java.io.IOException;   import java.io.PrintWriter;      import javax.servlet.ServletException;   import javax.servlet.http.HttpServlet;

相关推荐

推荐阅读