【LeetCode力扣】297. 二叉树的序列化与反序列化

这篇具有很好参考价值的文章主要介绍了【LeetCode力扣】297. 二叉树的序列化与反序列化。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言 

目录

1、题目介绍

2、解题思路 

2.1、详细过程图解

2.2、代码描述 

 2.3、完整代码


【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

 

1、题目介绍

原题链接:297. 二叉树的序列化与反序列化 - 力扣(LeetCode)

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

 示例 1:

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

输入: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

2、解题思路 

二叉树序列化就是将内存中的二叉树变成硬盘中的字符串形式,并且要求每个二叉树能够对应一个唯一的字符串。

二叉树反序列化就是将这个唯一字符串在内存中还原回对应的二叉树。

2.1、详细过程图解

这里采用先序遍历完成序列化。只要理解了一种遍历的序列化,其他遍历(包括不限于中序遍历、后序遍历、层次遍历)的序列化都是依葫芦画瓢了。

先说规则:

  • 通过先序遍历的顺序进行访问二叉树,假如访问到结点1,就将1写入字符串中,同理结点2就是写入2到节点中
  • 如果遇到空结点则在字符串中存入一个标识符号,这里我采用井号 # 来表述空结点。
  • 同时两个节点之间需要使用下划线 _ 隔开,也可以理解为表示一个结点值的结束。

序列化过程图解:

开始时字符串str为空。按照先序遍历,首先是访问结点1,所以此时字符串中存入了1和表示结点值结束的下划线 _。

str[ ]= "1_"

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

接着先序遍历访问到结点2,继续将2和下划线_拼接进字符串str中。

str[ ]= "1_2_"

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

接着先序遍历访问到空结点,此时将表示空姐点的标识符号井号#下划线_拼接进字符串str中。

str[ ]= "1_2_#_"

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

同理依次进行遍历

str[ ]= "1_2_#_#_"

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

通过依次遍历最后得到str字符串

str[ ]= "1_2_#_#_3_4_#_#_5_#_#_"

这个str字符串即为二叉树的序列化,而用字符串通过先序遍历还原回二叉树就成为反序列化。

反序列化过程图解:

str从前往后遍历,按照先序遍历【头左右】的顺序还原回二叉树。

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

 

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

 

 依次遍历str最终完成还原回原二叉树。

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

 

2.2、代码描述 

使用递归将二叉树按照先序遍历生成对应的序列化字符串ret。

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)   //等于空时返回井号标识符
        {
            return "#_";
        }
        String res = root.val + "_";  //将结点值与下划线_拼接
        res += serialize(root.left);  //将左子树返回的字符串拼接到当前的ret后
        res += serialize(root.right); //将右子树返回的字符串拼接到当前的ret后
        return ret;
    }

使用split方法对字符串进行拆分,拆分出来的值放入一个数组中,再用队列依次接收数组的 值。

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] val = data.split("_");  //将data字符串按照下划线_为分隔符对字符串进行拆分
        Queue<String> queue = new  LinkedList<>(); //队列
        for(int i = 0;i < val.length; i++) 
        {
            queue.add(val[i]);   //将拆分出来的值依次入队
        }
        return reconPreOrder(queue);  //返回队列
    }

将得到的队列依次出队,通过递归判断是否为空标识符井号#,是则返回null,否则将值存入新开辟的头结点root中,再通过递归方式创建左子树以及右子树。最后将头结点root返回,即完成二叉树的反序列化。

    public static TreeNode reconPreOrder(Queue<String> queue)
    {
        String val = queue.poll();   //出队
        if(val.equals("#"))   //等于#则返回null
        {
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(val));   //创建头结点存放val值
        root.left = reconPreOrder(queue);   //从递归中获取左子树信息
        root.right = reconPreOrder(queue);  //从递归中获取右子树信息

        return root;   //最后返回头结点
    }

 2.3、完整代码

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

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)
        {
            return "#_";
        }
        String res = root.val + "_";
        res += serialize(root.left);
        res += serialize(root.right);
        return res;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] val = data.split("_");
        Queue<String> queue = new  LinkedList<>();
        for(int i = 0;i < val.length; i++)
        {
            queue.add(val[i]);
        }
        return reconPreOrder(queue);
    }

    public static TreeNode reconPreOrder(Queue<String> queue)
    {
        String val = queue.poll();
        if(val.equals("#"))
        {
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(val));
        root.left = reconPreOrder(queue);
        root.right = reconPreOrder(queue);

        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));

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

彩蛋:

在查看其他题解时发现了一个有趣的解题方法(请勿模仿)哈哈哈哈哈

 

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言


 

关于二叉树遍历的精讲:

【算法与数据结构】二叉树的三种遍历代码实现(上)—— 用递归序知识点讲解_Hacynn的博客-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133609612?spm=1001.2014.3001.5502【算法与数据结构】二叉树的三种遍历代码实现(下)—— 非递归方式实现(大量图解)-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133669283?spm=1001.2014.3001.5502

 

【LeetCode力扣】297. 二叉树的序列化与反序列化,LeetCode刷题,算法,leetcode,数据结构,java,c语言

如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!文章来源地址https://www.toymoban.com/news/detail-713948.html

如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!

如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!

到了这里,关于【LeetCode力扣】297. 二叉树的序列化与反序列化的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包