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

 

目录

1、题目介绍

2、解题思路 

2.1、详细过程图解

2.2、代码描述 

 2.3、完整代码

 

1、题目介绍

原题链接：297. 二叉树的序列化与反序列化 - 力扣（LeetCode）

 示例 1：

输入：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_"

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

str[ ]= "1_2_"

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

str[ ]= "1_2_#_"

同理依次进行遍历

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

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

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

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

反序列化过程图解：

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

 

 

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

 

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 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 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 queue = new  LinkedList<>();
        for(int i = 0;i < val.length; i++)
        {
            queue.add(val[i]);
        }
        return reconPreOrder(queue);
    }
 
    public static TreeNode reconPreOrder(Queue 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));

彩蛋：

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

 

---

 

关于二叉树遍历的精讲：

【算法与数据结构】二叉树的三种遍历代码实现（上）—— 用递归序知识点讲解_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

 

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

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

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