您好,欢迎来到网暖!

当前位置:网暖 » 站长资讯 » 建站基础 » 网络技术 » 文章详细 订阅RssFeed

(lintcode)第7题二叉树的序列化和反序列化

来源:网络整理 浏览:232次 时间:2021-10-20

设计一个算法,并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”,读取文件后重建同样的二叉树被称为“反序列化”。

如何反序列化或序列化二叉树是没有限制的,你只需要确保可以将二叉树序列化为一个字符串,并且可以将字符串反序列化为原来的树结构。

给出一个测试数据样例, 二叉树{3,9,20,#,#,15,7},表示如下的树结构:

3

/  \

9   20

    /    \

  15    7

数据是按照BFS遍历得到的,BFS遍历也叫广度优先搜索,以上面的为例子,就是一层一层地遍历,第一层,遍历得到3,第二层遍历得到9和10,第三层遍历得到#,#,15,7。

下面是实现的代码:

/** * Definition of TreeNode: * public class TreeNode { *     public int val;//节点的值 *     public TreeNode left, right;//左右节点 *     public TreeNode(int val) { *         this.val = val;//初始化节点 *         this.left = this.right = null;//将左右节点置为0 *     } * } */class Solution {/** * This method will be invoked first, you should design your own algorithm * to serialize a binary tree which denote by a root node to a string which * can be easily deserialized by your own "deserialize" method later. */public static Queuequeue = new LinkedList<>();//用于保存将树结构序列化成字符串时使用来保存 public static Queuedataqueue = new LinkedList<>();//用于将字符串结构反序列化成树时使用来保存节点public String string = "";public String serialize(TreeNode root) {// write your code hereif (root == null) {//如果根节点为空,整棵树为空,返回“#”return "#";} else {queue.add(root);、、根节点不为空,加入队列while (!queue.isEmpty()) {//直到队列为空,才跳出循环TreeNode treeNode = queue.poll();//每次取出队列的第一的节点if (treeNode == null)//如果为空,那么直接输出“#”,不再把该点的左右子节点加入队列string = string + "#" + ",";else {//该节点不为空,则把该点的值加上在字符串后面        string = string + treeNode.val + ",";queue.add(treeNode.left);//该节点不为空,那么它的左右子节点都要加进去,可能为空,可能不为空,加进去不判断queue.add(treeNode.right);//从队列中取出来才判断是不是为空,为空则没有下一层了}}}string = string.substring(0, string.length() - 2);//将后面的“,”去掉return string;}/** * This method will be invoked second, the argument data is what exactly you * serialized at method "serialize", that means the data is not given by * system, it's given by your own serialize method. So the format of data is * designed by yourself, and deserialize it here as you serialize it in * "serialize" method. */public TreeNode deserialize(String data) {// write your code hereString[] strs = data.split(",");//根据“,”来分隔成为字符串数组if (strs.length == 0||data.equals("#")) {//判断字符串数组是等于#或者为空TreeNode rooTreeNode = null;return rooTreeNode;//直接返回空根节点} else {//数组中至少有一个元素TreeNode rootNode = new TreeNode(Integer.parseInt(strs[0]));//拿到数组的第一个元素dataqueue.add(rootNode);//把根节点加进去队列中(思路是把已经创建好的节点加进去队列中)int i = 1;下次取出第二个元素while (!dataqueue.isEmpty() && i < strs.length) {//直到队列为空,或者数组中元素被取完了TreeNode treeNode = dataqueue.poll();//每次弹出队列的第一个节点,分别构造左右节点if (strs[i].equals("#")) {//如果等于“#”,那么取出来的这个节点的左节点为空treeNode.left = null;i++;} else {//如果不是空节点,那么我们要把这个节点加入队列中,这意味着这个节点可能还有子节点treeNode.left = new TreeNode(Integer.parseInt(strs[i]));dataqueue.add(treeNode.left);i++;}//下面接着判断右节点,注意,有可能数组被取光了,也就是没有右节点了if (i < strs.length&&strs[i].equals("#") ) {treeNode.right = null;i++;} else if(i < strs.length&& !strs[i].equals("#")){treeNode.right = new TreeNode(Integer.parseInt(strs[i]));dataqueue.add(treeNode.right);i++;}}return rootNode;}}}//在上面,最主要的是使用了队列的数据结构,然后把第一个节点加进去(不为空),再每次从队列中取出节点,直到队列中的节点被取完,当然,在循环中,如果符合条件(节点不为空,//就会往队列中加入节点),这样就实现了,同一层的都是挨着加入队列的,出来的时候,也是紧挨着的,而不是不断递归到最底层,优先忽略了同一层的其他节点。

如果有所帮助,脸皮厚求个赞~

此文章仅代表自己(本菜鸟)学习积累记录,或者学习笔记,如有侵权,请联系作者删除。人无完人,文章也一样,文笔稚嫩,在下不才,勿喷,如果有错误之处,还望指出,感激不尽~

技术之路不在一时,山高水长,纵使缓慢,驰而不息。

公众号:秦怀杂货店

 

 

推荐站点

  • 腾讯腾讯

    腾讯网(www.QQ.com)是中国浏览量最大的中文门户网站,是腾讯公司推出的集新闻信息、互动社区、娱乐产品和基础服务为一体的大型综合门户网站。腾讯网服务于全球华人用户,致力成为最具传播力和互动性,权威、主流、时尚的互联网媒体平台。通过强大的实时新闻和全面深入的信息资讯服务,为中国数以亿计的互联网用户提供富有创意的网上新生活。

    www.qq.com
  • 搜狐搜狐

    搜狐网是全球最大的中文门户网站,为用户提供24小时不间断的最新资讯,及搜索、邮件等网络服务。内容包括全球热点事件、突发新闻、时事评论、热播影视剧、体育赛事、行业动态、生活服务信息,以及论坛、博客、微博、我的搜狐等互动空间。

    www.sohu.com
  • 网易网易

    网易是中国领先的互联网技术公司,为用户提供免费邮箱、游戏、搜索引擎服务,开设新闻、娱乐、体育等30多个内容频道,及博客、视频、论坛等互动交流,网聚人的力量。

    www.163.com
  • 新浪新浪

    新浪网为全球用户24小时提供全面及时的中文资讯,内容覆盖国内外突发新闻事件、体坛赛事、娱乐时尚、产业资讯、实用信息等,设有新闻、体育、娱乐、财经、科技、房产、汽车等30多个内容频道,同时开设博客、视频、论坛等自由互动交流空间。

    www.sina.com.cn
  • 百度一下百度一下

    百度一下,你就知道

    www.baidu.com