柳州专业做网站,wap网站为什么没有了,网站兼容所有浏览器,wordpress语言包更新目录
1、题目介绍
2、解题思路
2.1、详细过程图解
2.2、代码描述 2.3、完整代码 1、题目介绍
原题链接#xff1a;297. 二叉树的序列化与反序列化 - 力扣#xff08;LeetCode#xff09; 示例 1#xff1a; 输入#xff1a;root [1,2,3,null,null,4,5] 输出#…
目录
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字符串按照下划线_为分隔符对字符串进行拆分QueueString 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(QueueString 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(_);QueueString queue new LinkedList();for(int i 0;i val.length; i){queue.add(val[i]);}return reconPreOrder(queue);}public static TreeNode reconPreOrder(QueueString 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?spm1001.2014.3001.5502【算法与数据结构】二叉树的三种遍历代码实现下—— 非递归方式实现大量图解-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133669283?spm1001.2014.3001.5502 如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
