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

Wesley13
• 阅读 819

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

It's easy to find if you know what you're looking for.

如果你知道自己想追求什么,就很容易成功。

问题描述

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

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

示例:

你可以将以下二叉树:

1

/ \

2   3

/ \

4   5

序列化为 "[1,2,3,null,null,4,5]"

BFS解决

这题上面说了一大堆,其实就是把二叉树转化为一个字符串,并且还能把这个字符串还原成原来的二叉树就可以了。

把二叉树转化为字符串可以有很多种方式,比如前序遍历,中序遍历,后续遍历,BFS,DFS都是可以的,对于树的各种遍历具体可以看下373,数据结构-6,树。但这题还要求把字符串再还原成原来的二叉树。最容易想到的就是BFS,就是一层一层从往下遍历

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

来看下代码

 1public class Codec { 2 3    //把树转化为字符串(使用BFS遍历) 4    public String serialize(TreeNode root) { 5        //边界判断,如果为空就返回一个字符串"#" 6        if (root == null) 7            return "#"; 8        //创建一个队列 9        Queue<TreeNode> queue = new LinkedList<>();10        StringBuilder res = new StringBuilder();11        //把根节点加入到队列中12        queue.add(root);13        while (!queue.isEmpty()) {14            //节点出队15            TreeNode node = queue.poll();16            //如果节点为空,添加一个字符"#"作为空的节点17            if (node == null) {18                res.append("#,");19                continue;20            }21            //如果节点不为空,把当前节点的值加入到字符串中,22            //注意节点之间都是以逗号","分隔的,在下面把字符23            //串还原二叉树的时候也是以逗号","把字符串进行拆分24            res.append(node.val + ",");25            //左子节点加入到队列中(左子节点有可能为空)26            queue.add(node.left);27            //右子节点加入到队列中(右子节点有可能为空)28            queue.add(node.right);29        }30        return res.toString();31    }3233    //把字符串还原为二叉树34    public TreeNode deserialize(String data) {35        //如果是"#",就表示一个空的节点36        if (data == "#")37            return null;38        Queue<TreeNode> queue = new LinkedList<>();39        //因为上面每个节点之间是以逗号","分隔的,所以这里40        //也要以逗号","来进行拆分41        String[] values = data.split(",");42        //上面使用的是BFS,所以第一个值就是根节点的值,这里创建根节点43        TreeNode root = new TreeNode(Integer.parseInt(values[0]));44        queue.add(root);45        for (int i = 1; i < values.length; i++) {46            //队列中节点出栈47            TreeNode parent = queue.poll();48            //因为在BFS中左右子节点是成对出现的,所以这里挨着的两个值一个是49            //左子节点的值一个是右子节点的值,当前值如果是"#"就表示这个子节点50            //是空的,如果不是"#"就表示不是空的51            if (!"#".equals(values[i])) {52                TreeNode left = new TreeNode(Integer.parseInt(values[i]));53                parent.left = left;54                queue.add(left);55            }56            //上面如果不为空就是左子节点的值,这里是右子节点的值,注意这里有个i++,57            if (!"#".equals(values[++i])) {58                TreeNode right = new TreeNode(Integer.parseInt(values[i]));59                parent.right = right;60                queue.add(right);61            }62        }63        return root;64    }65}

DFS解决

DFS遍历是从根节点开始,一直往左子节点走,当到达叶子节点的时候会返回到父节点,然后从从父节点的右子节点继续遍历……

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

 1class Codec { 2 3    //把树转化为字符串(使用DFS遍历,也是前序遍历,顺序是:根节点→左子树→右子树) 4    public String serialize(TreeNode root) { 5        //边界判断,如果为空就返回一个字符串"#" 6        if (root == null) 7            return "#"; 8        return root.val + "," + serialize(root.left) + "," + serialize(root.right); 9    }1011    //把字符串还原为二叉树12    public TreeNode deserialize(String data) {13        //把字符串data以逗号","拆分,拆分之后存储到队列中14        Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));15        return helper(queue);16    }1718    private TreeNode helper(Queue<String> queue) {19        //出队20        String sVal = queue.poll();21        //如果是"#"表示空节点22        if ("#".equals(sVal))23            return null;24        //否则创建当前节点25        TreeNode root = new TreeNode(Integer.valueOf(sVal));26        //分别创建左子树和右子树27        root.left = helper(queue);28        root.right = helper(queue);29        return root;30    }31}

总结

把二叉树转化为字符串很简单,关键是怎么把转化的字符串再还原成原来的二叉树,这里使用BFS和DFS都很容易实现。

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

442,剑指 Offer-回溯算法解二叉树中和为某一值的路径

440,剑指 Offer-从上到下打印二叉树 II

434,剑指 Offer-二叉树的镜像

387,二叉树中的最大路径和

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

长按上图,识别图中二维码之后即可关注。

如果觉得有用就点个"赞"吧

本文分享自微信公众号 - 数据结构和算法(sjjghsf)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
Android So动态加载 优雅实现与原理分析
背景:漫品Android客户端集成适配转换功能(基于目标识别(So库35M)和人脸识别库(5M)),导致apk体积50M左右,为优化客户端体验,决定实现So文件动态加载.!(https://oscimg.oschina.net/oscnet/00d1ff90e4b34869664fef59e3ec3fdd20b.png)点击上方“蓝字”关注我
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
9个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这