【数据结构】二叉树篇|超清晰图解和详解:二叉树的序列化和反序列化

这篇具有很好参考价值的文章主要介绍了【数据结构】二叉树篇|超清晰图解和详解:二叉树的序列化和反序列化。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构】二叉树篇|超清晰图解和详解:二叉树的序列化和反序列化,数据结构|刷题专栏,数据结构,数据库,二叉树,算法,java

  • 博主简介:努力学习的22级计算机科学与技术本科生一枚🌸
  • 博主主页: @是瑶瑶子啦
  • 每日一言🌼: 你不能要求一片海洋,没有风暴,那不是海洋,是泥塘——毕淑敏

一、核心

  • 🍊 序列化:本质就是二叉树的遍历,就那么几个:前序、中序、后序、层序。而序列化只不过就是在遍历到节点时,把它记录下来,空节点也是节点,也要记录(一般就是#)。
  • 🍊反序列化:字符串构建二叉树,本质是子问题,也就是递归。

其实在前面纲领篇就(🔗【数据结构】二叉树篇| 纲领&思路01+刷题)过,序列化的本质就是第一种解题思路——遍历一遍二叉树即可解题;反序列化是第二种解题思路——需要递归,利用子问题来构建二叉树。所谓的序列化和反序列,只不过也是唬人的名头罢了。
【数据结构】二叉树篇|超清晰图解和详解:二叉树的序列化和反序列化,数据结构|刷题专栏,数据结构,数据库,二叉树,算法,java

【数据结构】二叉树篇|超清晰图解和详解:二叉树的序列化和反序列化,数据结构|刷题专栏,数据结构,数据库,二叉树,算法,java

二、题目

🔗297. 二叉树的序列化与反序列化
【数据结构】二叉树篇|超清晰图解和详解:二叉树的序列化和反序列化,数据结构|刷题专栏,数据结构,数据库,二叉树,算法,java

/**
 * 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) {
        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        
    }
}

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

【数据结构】二叉树篇|超清晰图解和详解:二叉树的序列化和反序列化,数据结构|刷题专栏,数据结构,数据库,二叉树,算法,java

注意:序列化的具体格式没有要求,下面统一按照这种格式:1,2,#,4,#,#,3,#,#,

2.1:前序遍历

【数据结构】二叉树篇|超清晰图解和详解:二叉树的序列化和反序列化,数据结构|刷题专栏,数据结构,数据库,二叉树,算法,java

  • 前序遍历_序列化
	String SEP = ",";//分隔符,用来分隔每个节点
    String NULL = "#";//表示当前节点为null

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();//用来装字符串的容器
        //遍历函数
        serialize(root, sb);
        return sb.toString();
    }
    public void serialize(TreeNode root, StringBuilder sb){
        //进行前序遍历
        if (root == null){
            sb.append(NULL).append(SEP);
        }
        /*******前序位置 */
        sb.append(root.val).append(SEP);
        /****************/
        serialize(root.left, sb);
        serialize(root.right, sb);
    }

PS:一般语境下,单单前序遍历结果是不能还原二叉树结构的,因为缺少空指针的信息,至少要得到前、中、后序遍历中的两种才能还原二叉树。但是这里的 node 列表包含空指针的信息,所以只使用 node 列表就可以还原二叉树。

  • 前序遍历_反序列化
	 // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        //用来存储前序序列及其节点,方便逐个拿出构建二叉树
        LinkedList<String> nodes = new LinkedList<>();
        for (String node : data.split(SEP)){
            nodes.addLast(node);
        }
        return deserialize(nodes);
    }
    public TreeNode deserialize(LinkedList<String> nodes){

        if(nodes.isEmpty()){
            return null;
        }
        /****** 前序遍历位置 ******/
        // 列表最左侧就是根节点
        String first = nodes.removeFirst();
        if (first.equals(NULL)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(first));//不为空,构建根节点
        /*********************** */
        root.left = deserialize(nodes);
        root.right = deserialize(nodes);

        return root;
    }

至于其他遍历的解法,本质还是一样,序列化的本质就是遍历二叉树,反序列化的本质就是构建子问题,这里就不一一详解。

2.2:完整代码

/**
 * 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 = "#";//表示当前节点为null

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();//用来装字符串的容器
        //遍历函数
        serialize(root, sb);
        return sb.toString();
    }
    public void serialize(TreeNode root, StringBuilder sb){
        //进行前序遍历
        if (root == null){
            sb.append(NULL).append(SEP);
            return;
        }
        /*******前序位置 */
        sb.append(String.valueOf(root.val)).append(SEP);
        /****************/
        serialize(root.left, sb);
        serialize(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        //用来存储前序序列及其节点,方便逐个拿出构建二叉树
        LinkedList<String> nodes = new LinkedList<>();
        for (String node : data.split(SEP)){
            nodes.addLast(node);
        }
        return deserialize(nodes);
    }
    public TreeNode deserialize(LinkedList<String> nodes){

        if(nodes.isEmpty()){
            return null;
        }
        /****** 前序遍历位置 ******/
        // 列表最左侧就是根节点
        String first = nodes.removeFirst();
        if (first.equals(NULL)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(first));//不为空,构建根节点
        /*********************** */
        root.left = deserialize(nodes);
        root.right = deserialize(nodes);

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

💐若有疑问的地方,欢迎随时在评论区or私信找瑶瑶子交流讨论🌺

【数据结构】二叉树篇|超清晰图解和详解:二叉树的序列化和反序列化,数据结构|刷题专栏,数据结构,数据库,二叉树,算法,java

  • Java岛冒险记【从小白到大佬之路】

  • LeetCode每日一题–进击大厂

  • Go语言核心编程

  • 算法文章来源地址https://www.toymoban.com/news/detail-686122.html

到了这里,关于【数据结构】二叉树篇|超清晰图解和详解:二叉树的序列化和反序列化的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构---手撕图解二叉树(含大量递归图解)

    二叉树的几乎所有实现都是依靠递归实现,递归的核心思路是把任何一个二叉树看成根和左右子树,而二叉树递归的核心玩法就是把二叉树的左右子树再看成根,再找左右子树,再看成根… 因此,解决二叉树问题实际上要把二叉树转换成一个一个子树的过程,找到一个一个的

    2024年02月16日
    浏览(42)
  • 数据结构:手撕图解二叉树(含大量递归图解)

    二叉树的几乎所有实现都是依靠递归实现,递归的核心思路是把任何一个二叉树看成根和左右子树,而二叉树递归的核心玩法就是把二叉树的左右子树再看成根,再找左右子树,再看成根… 因此,解决二叉树问题实际上要把二叉树转换成一个一个子树的过程,找到一个一个的

    2024年02月15日
    浏览(52)
  • 【算法与数据结构】二叉树的三种遍历代码实现(下)—— 非递归方式实现(大量图解)

     上篇: 【算法与数据结构】二叉树的三种遍历代码实现(上)—— 用递归序知识点讲解_Hacynn的博客-CSDN博客 https://blog.csdn.net/zzzzzhxxx/article/details/133609612?spm=1001.2014.3001.5502 目录 前言 1、先序遍历 1.1、详细图解描述 1.2、先序遍历非递归代码实现  2、中序遍历 2.1、详细图解描

    2024年02月08日
    浏览(39)
  • 数据结构刷题篇 之 【力扣二叉树基础OJ】详细讲解(含每道题链接及递归图解)

    有没有一起拼用银行卡的,取钱的时候我用,存钱的时候你用 难度等级:⭐ 直达链接:相同的树 难度等级:⭐ 直达链接:单值二叉树 难度等级:⭐⭐ 直达链接:对称二叉树 难度等级:⭐⭐⭐ 直达链接:二叉树的前序遍历 难度等级:⭐⭐⭐⭐ 直达链接:另一颗子树 注:

    2024年04月16日
    浏览(80)
  • 【数据结构】队列篇| 超清晰图解和详解:循环队列模拟、用栈实现队列、用队列实现栈

    博主简介: 努力学习的22级计算机科学与技术本科生一枚🌸 博主主页: @是瑶瑶子啦 每日一言🌼: 每一个不曾起舞的日子,都是对生命的辜负。——尼采 🔗622. 设计循环队列 👧🏻 思路: 🍊数据结构: 使用数组为数据结构,且采用牺牲一个空间的方法来包装判空和判满的

    2024年02月11日
    浏览(40)
  • 【数据结构-二叉树】二叉树

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月07日
    浏览(48)
  • 数据结构:搜索二叉树 | 平衡二叉树

    博客写的代码都放在这里:gitee仓库链接 1.二叉搜索树 1.1.基本概念 二叉搜索树又称二叉排序树, 可以为空,如果不为空具有以下性质的二叉树 : 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的

    2024年01月23日
    浏览(58)
  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研

    2024年01月25日
    浏览(63)
  • 【数据结构】二叉树——链式结构

    目录  一、前置声明 二、二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 三、节点个数以及高度 3.1 节点个数 3.2 叶子节点个数 3.3 第k层节点个数 3.4 二叉树的高度/深度 3.5 查找值为x的节点 四、二叉树的创建和销毁 4.1 构建二叉树 4.2 二叉树销毁 4.3 判断二叉树

    2024年02月16日
    浏览(47)
  • 【数据结构】二叉树——顺序结构

    由于每个节点都 只有一个父节点 ,所以我们可通过双亲来表示一棵树。具体方式通过 数组的形式 实现。 根节点的下标为0 按照层序从上到下排序 每层从左向右递增 表示形式: 二维数组 数据的列标为0 ,只需确定行标,即可锁定位置 根节点的父节点下标为 -1 列标为1存父节

    2024年02月02日
    浏览(56)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包