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

2023-10-15 10:36

本文主要是介绍【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<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));

彩蛋:

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

 


 

关于二叉树遍历的精讲:

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

 

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

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

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

这篇关于【LeetCode力扣】297. 二叉树的序列化与反序列化的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/217108

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划