《二叉树序列化与反序列化：实现方法与细节解析》

前言

依赖：二叉树遍历算法细节与优化方案
本篇涉及谈谈二叉树的序列化问题。先序后序层序序列化以及反序列化的问题 中序序列化是不行的, 下面会给出解释

刷题网站:洛谷，leetcode, 牛客网。网站链接自寻！
参考: 《程序员代码面试指南》 & 代码随想录。每道题后我都会附带链接，代码会上传到GitHub上
基础部分简略(任意教材都能找到的内容，初学者都会的内容); 进阶部分有一定思考难度和coding挑战;拓展部分学得更加有深度。上难度的平衡树有序表(treap, spaly, 红黑树这些)基本不会涉及。
编程语言: 笔者热爱Java, Java为主，目前该模块并没有提供其它语言版本。 -借助chatgpt转换成自己的语言吧！
IDE：Intellij IDEA。主题: MonoKai pro ; 字体: Fira cod light。
容器和算法技巧: 栈，队列，哈希表，数组；递归，分治，对于部分可以使用动态规划的题也会提供解释。读者应当可以用数组手搓栈和队列结构

提示：

题目通过000~999进行编号，不过网站暂未提供目录结构无法快速寻找相关题目（不好意思）🥲。
标题可以点击跳转页面。每道题都配有相关链接。函数题一般是leetcode, acm风格是牛客和洛谷的。处理输入输出的题的类里多数有main函数可以自行运行测试。
每道题都可以ctrl + c, ctrl + v提交。注意:修改类名，函数名，不要提交无关的类。
思考和coding, 而不是注重题量和速度哦。😘

013 先序遍历序列化和反序列化

内存中二叉树结构如何得以保存。我们知道内存断电(没有任何服务会永远进行)会丢数据。
硬盘可以持久化地保存文件。如何将二叉树保存在硬盘上呢?
文件是文本内容，就是一堆字符串。
序列化本质是一种映射关系。只有将二叉树映射出一个字符串，并且保证字符串能在内存中调用函数还原出这个二叉树，就可以说是间接保存了这颗二叉树。
二叉树->字符串:称作二叉树的序列化。
字符串->二叉树:称作二叉树的反序列化。

013是根据先序遍历构建的。
序列化反序列化可以根据后序遍历和层序遍历构建对应的字符串。
中序遍历不行，后面会举例说明。

如何唯一能保证字符串和二叉树结构对应唯一呢?

       A/ \B   C/ \   \D   E   F

先序序列化结果:
A,B,D,#,#,E,#,#,C,#,F,#,

用,作为节点分隔符；用#替代null（或空节点）。

代码:

//注意修改类名->Solution
//测试链接: https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
public class Coding006_PreorderSerializeAndDeserialize {//不要提交这个类public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}// Encodes a tree to a single string.public String serialize(TreeNode root) {//创建一个可变字符串类StringBuilder类// 字符串高效增加元素。StringBuilder builder = new StringBuilder();//辅助调用f(root, builder);return builder.toString();//转String}//public void f(TreeNode root, StringBuilder builder){if(root == null){builder.append("#,");}else {//链式调用builder.append(root.val).append(",");f(root.left, builder);f(root.right, builder);}}//全局变量追踪当前字符public static int cnt = 0;// Decodes your encoded data to tree.public TreeNode deserialize(String data) {//根据分割符","切割字符串 ->字符串数组。String[] vals = data.split(",");cnt = 0;return g(vals);//调用辅助方法}public TreeNode g(String[] vals){//提取当前字符串String cur = vals[cnt++];if(cur.equals("#")){return null;}//递归: 生成当前节点 + 左子树连接递归 + 右子树连接递归。TreeNode head = new TreeNode(Integer.parseInt(cur));head.left = g(vals);head.right = g(vals);return head;//返回最终结果。}
}

014: 后序遍历序列化和反序列化

前置:013先序遍历序列化和反序列化
只需要在013基础上修改一些内容，就可以得到反序列化的代码了。
序列化过程: 递归构建字符串的过程改成后序顺序。
反序列化过程的根节点应该切割后字符串的最后一个位置，然后按照右左顺序复原树即可。

注意修改类名->Solution
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
public class Coding007_PostorderSerializeAndDeserialize {//不要提交这个类public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}// Encodes a tree to a single string.public String serialize(TreeNode root) {//创建一个可变字符串类StringBuilder类// 字符串高效增加元素。StringBuilder builder = new StringBuilder();//辅助调用f(root, builder);return builder.toString();//转String}//public void f(TreeNode root, StringBuilder builder){if(root == null){builder.append("#,");}else {f(root.left, builder);f(root.right, builder);builder.append(root.val).append(",");}}//全局变量追踪当前字符public static int cnt = 0;// Decodes your encoded data to tree.public TreeNode deserialize(String data) {//根据分割符","切割字符串 ->字符串数组。String[] vals = data.split(",");cnt = vals.length-1;return g(vals);//调用辅助方法}public TreeNode g(String[] vals){//提取当前字符串String cur = vals[cnt--];if(cur.equals("#")){return null;}TreeNode head = new TreeNode(Integer.parseInt(cur));head.right = g(vals);head.left = g(vals);return head;}
}

015: 层序遍历序列化和反序列化

前置:
013先序遍历序列化和反序列化, 了解序列化和反序列化的概念即可。
008经典层序遍历

看过以上前置，可以直接阅读代码部分即可

//二叉树的层序序列化和反序列化
public class Coding008_LevelorderSerializeAndDeserialize {//不要提交这个类public static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int v) {val = v;}}//提交这个类1public class Codec {public static int MAX = 10001;public static TreeNode[] queue = new TreeNode[MAX];public static int l,r;public String serialize(TreeNode root){StringBuilder builder = new StringBuilder();if(root != null){builder.append(root.val).append(",");l = r = 0;queue[r++] = root;while(l != r){//这里复用root。root = queue[l++];//经典的bfs操作即可。 只需注意， 如果孩子为空应该以"#,"的形式存入。if(root.left != null){queue[r++] = root.left;builder.append(root.left.val).append(",");}else{builder.append("#").append(",");}if(root.right != null){queue[r++] = root.right;builder.append(root.right.val).append(",");}else{builder.append("#").append(",");}}}return builder.toString();}/*** * @param val 字符串* @return 根据字符串是否为空串返回节点。*/private static TreeNode generate(String val){return val.equals("#") ? null : new TreeNode(Integer.parseInt(val));}public TreeNode deserialize(String data) {if(data.isEmpty()){return null;}//根据分割符","切割字符串String[] vals = data.split(",");int cnt = 0;//记录当前字符串数组的有效值l = r = 0;//重置TreeNode root = generate(vals[cnt++]);queue[r++] = root;while(l != r){//按顺序挨个处理TreeNode cur = queue[l++];//连接左右孩子cur.left = generate(vals[cnt++]);cur.right = generate(vals[cnt++]);//根据cur的左右孩子是否为空决定入队。if(cur.left != null){queue[r++] = cur.left;}if(cur.right != null){queue[r++] = cur.right;}}return root;}}
}