[LintCode] Serialize and Deserialize Binary Tree(二叉树的序列化和反序列化)
描述
设计一个算法,并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”,读取文件后重建同样的二叉树被称为“反序列化”。
如何反序列化或序列化二叉树是没有限制的,你只需要确保可以将二叉树序列化为一个字符串,并且可以将字符串反序列化为原来的树结构。
对二进制树进行反序列化或序列化的方式没有限制,LintCode将您的serialize
输出作为deserialize
的输入,它不会检查序列化的结果。
样例
给出一个测试数据样例, 二叉树{3,9,20,#,#,15,7}
,表示如下的树结构:
3 / \ 9 20 / \ 15 7
我们的数据是进行 BFS 遍历得到的。当你测试结果 wrong answer时,你可以作为输入调试你的代码。
你可以采用其他的方法进行序列化和反序列化。
代码
GitHub 的源代码,请访问下面的链接:
package com.ossez.lang.tutorial.tests.lintcode; import java.util.ArrayList; import org.junit.Test; import org.slf4j.Logger; import org.slf4j.LoggerFactory; import com.ossez.lang.tutorial.models.TreeNode; /** * <p> * 7 * <ul> * <li>@see <a href= * "https://www.cwiki.us/display/ITCLASSIFICATION/Serialize+and+Deserialize+Binary+Tree">https://www.cwiki.us/display/ITCLASSIFICATION/Serialize+and+Deserialize+Binary+Tree</a> * <li>@see<a href= * "https://www.lintcode.com/problem/serialize-and-deserialize-binary-tree">https://www.lintcode.com/problem/serialize-and-deserialize-binary-tree</a> * </ul> * </p> * * @author YuCheng * */ public class LintCode0007SerializeAndDeserialize { private final static Logger logger = LoggerFactory.getLogger(LintCode0007SerializeAndDeserialize.class); /** * */ @Test public void testMain() { logger.debug("BEGIN"); String data = "{3,9,20,#,#,15,7}"; System.out.println(serialize(deserialize(data))); } /** * Deserialize from array to tree * * @param data * @return */ private TreeNode deserialize(String data) { // NULL CHECK if (data.equals("{}")) { return null; } ArrayList<TreeNode> treeList = new ArrayList<TreeNode>(); data = data.replace("{", ""); data = data.replace("}", ""); String[] vals = data.split(","); // INSERT ROOT TreeNode root = new TreeNode(Integer.parseInt(vals[0])); treeList.add(root); int index = 0; boolean isLeftChild = true; for (int i = 1; i < vals.length; i++) { if (!vals[i].equals("#")) { TreeNode node = new TreeNode(Integer.parseInt(vals[i])); if (isLeftChild) { treeList.get(index).left = node; } else { treeList.get(index).right = node; } treeList.add(node); } // LEVEL if (!isLeftChild) { index++; } // MOVE TO RIGHT OR NEXT LEVEL isLeftChild = !isLeftChild; } return root; } /** * * @param root * @return */ public String serialize(TreeNode root) { // write your code here if (root == null) { return "{}"; } ArrayList<TreeNode> queue = new ArrayList<TreeNode>(); queue.add(root); for (int i = 0; i < queue.size(); i++) { TreeNode node = queue.get(i); if (node == null) { continue; } queue.add(node.left); queue.add(node.right); } while (queue.get(queue.size() - 1) == null) { queue.remove(queue.size() - 1); } StringBuilder sb = new StringBuilder(); sb.append("{"); sb.append(queue.get(0).val); for (int i = 1; i < queue.size(); i++) { if (queue.get(i) == null) { sb.append(",#"); } else { sb.append(","); sb.append(queue.get(i).val); } } sb.append("}"); return sb.toString(); } }
点评
本题目主要需要你对二叉树的遍历方法有所了解。
遍历二叉树主要有 2 类方法,分别为深度优先(DFS)和广度优先(BFS)。
在深度优先中,你有又可以使用前序,中序和后序搜索方法,你可以使用递归或者非递归算法实现。对于广度优先算法,一般都会采用非递归的实现方法进行实现。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
补习系列(15)-springboot 分布式会话原理
[TOC] 一、背景 在 补习系列(3)-springboot 几种scope 一文中,笔者介绍过 Session的部分,如下: 对于服务器而言,Session 通常是存储在本地的,比如Tomcat 默认将Session 存储在内存(ConcurrentHashMap)中。 但随着网站的用户越来越多,Session所需的空间会越来越大,同时单机部署的 Web应用会出现性能瓶颈。这时候需要进行架构的优化或调整,比如扩展Web 应用节点,在应用服务器节点之前实现负载均衡。 那么,这对现有的会话session 管理带来了麻烦,当一个带有会话表示的Http请求到Web服务器后,需求在请求中的处理过程中找到session数据,而 session数据是存储在本地的,假设我们有应用A和应用B,某用户第一次访问网站,session数据保存在应用A中;第二次访问,如果请求到了应用B,会发现原来的session并不存在! 一般,我们可通过集中式的 session管理来解决这个问题,即分布式会话。 [图 - ] 分布式会话 二、SpringBoot 分布式会话 在前面的文章中介绍过Redis 作为缓存读写的...
- 下一篇
SpringBoot中oauth2.0学习之服务端配置快速上手
现在第三方登录的例子数见不鲜。其实在这种示例当中,oauth2.0是使用比较多的一种授权登录的标准。oauth2.0也是从oauth1.0升级过来的。那么关于oauth2.0相关的概念及其原理,大家可以参考这篇文章,这篇文章中会有更详细的解释,下来我们直接进入正题。 1.1、gradle依赖 compile('org.springframework.cloud:spring-cloud-starter-oauth2') compile('org.springframework.cloud:spring-cloud-starter-security') 在这里我直接引入的是spring-cloud的依赖项,这种依赖的jar包更全面一些,这里面的核心基础还是spring-security。这里SpringBoot的版本为2.0.6.REALEASE 1.2、@EnableAuthorizationServer 在这里我着重强调一下这个注解:@EnableAuthorizationServer,这个注解源代码如下: @Target(ElementType.TYPE) @Retention(R...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS7,8上快速安装Gitea,搭建Git服务器
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- Docker安装Oracle12C,快速搭建Oracle学习环境
- Windows10,CentOS7,CentOS8安装Nodejs环境
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS8安装Docker,最新的服务器搭配容器使用
- 设置Eclipse缩进为4个空格,增强代码规范
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS7设置SWAP分区,小内存服务器的救世主