当前位置:网站首页>【剑指offer】序列化二叉树
【剑指offer】序列化二叉树
2022-07-06 08:46:00 【保住头发的破风小子】
解题思路
序列化时,可以通过各种遍历方法,例如层序遍历、递归遍历对二叉树进行遍历,遍历过程中将每个节点的值拼接到字符串中,注意每个节点之间用一个标识符隔开,例如,
,这是为了防止节点的值超过个位数。
反序列化则根据序列化的过程进行相应的解码,不同的反序列化方式有不同的技巧,下面分别使用层序遍历和先序遍历两种方法进行求解。
解法一:层序遍历
- 序列化:通过队列进行遍历,然后生成序列化的字符串,比较常规。
- 反序列化:稍微有点难度。首先对
res
按照,
进行切分得到String数组strs
,每个位置表示一个节点的值。和序列化一样,也需要使用一个队列进行操作,注意每次需要取数组strs
中的两个元素,即构建当前节点的左右子树,然后分别把左右子树加入队列中。
import java.util.*;
public class Solution {
String Serialize(TreeNode root) {
String str = "";
if (root == null)
return str;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
str += root.val + ",";
while (!queue.isEmpty()) {
TreeNode top = queue.poll();
if (top.left == null)
str += "#";
else {
queue.add(top.left);
str += top.left.val;
}
str += ',';
if (top.right == null)
str += "#";
else {
queue.add(top.right);
str += top.right.val;
}
str += ',';
}
return str;
}
TreeNode Deserialize(String str) {
if (str.length() == 0)
return null;
int i = 1;
String strList[] = str.split(",");
TreeNode root = new TreeNode(Integer.parseInt(strList[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode top = queue.poll();
// 左子树
if (strList[i].equals("#"))
top.left = null;
else {
top.left = new TreeNode(Integer.parseInt(strList[i]));
queue.add(top.left);
}
i++;
// 右子树
if (strList[i].equals("#"))
top.right = null;
else {
top.right = new TreeNode(Integer.parseInt(strList[i]));
queue.add(top.right);
}
i++;
}
return root;
}
}
解法二:先序遍历
- 序列化:定义全局字符串
res
,递归的时候记录遍历到的节点值,遍历完一个节点后,在其后加,
标识符。 - 反序列化:稍微有点难度。首先对
res
按照,
进行切分得到String数组strs
,每个位置表示一个节点的值。定义全局变量ind
,用来记录当前遍历到strs
的位置,如果当前位置是#
,表示为空,直接返回null
;否则新建一个节点node
,并递归构建其左右子树,注意,在递归前判断数组是否越界,如果inds++
后等于strs
的长度,则表明已经遍历完数组,此时返回node
(注意数组越界的判断不能放在开头,否则会写不下去,因为不知道返回什么了)
import java.util.*;
public class Solution {
public String res = "";
public int ind = 0;
String Serialize(TreeNode root) {
if (root == null) {
res += "#,";
return res;
}
res += root.val + ",";
Serialize(root.left);
Serialize(root.right);
return res;
}
TreeNode deserialize(String[] strs) {
if (strs[ind].equals("#")) {
ind++;
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(strs[ind]));
ind++;
if (ind >= strs.length)
return node;
node.left = deserialize(strs);
node.right = deserialize(strs);
return node;
}
TreeNode Deserialize(String str) {
String[] strs = str.split(",");
return deserialize(strs);
}
}
边栏推荐
- China Light conveyor belt in-depth research and investment strategy report (2022 Edition)
- 延迟初始化和密封类
- LeetCode:剑指 Offer 48. 最长不含重复字符的子字符串
- On the inverse order problem of 01 knapsack problem in one-dimensional state
- Research Report on Market Research and investment strategy of microcrystalline graphite materials in China (2022 Edition)
- 超高效!Swagger-Yapi的秘密
- LeetCode:124. 二叉树中的最大路径和
- The network model established by torch is displayed by torch viz
- visdom可视化实现与检查介绍
- Image, CV2 read the conversion and size resize change of numpy array of pictures
猜你喜欢
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
egg. JS project deployment online server
Mobile phones and computers on the same LAN access each other, IIS settings
查看局域网中电脑设备
LeetCode:236. 二叉树的最近公共祖先
Simple use of promise in uniapp
软件卸载时遇到trying to use is on a network resource that is unavailable
深度剖析C语言数据在内存中的存储
Excellent software testers have these abilities
电脑清理,删除的系统文件
随机推荐
LeetCode:26. 删除有序数组中的重复项
LeetCode:394. 字符串解码
LeetCode:剑指 Offer 42. 连续子数组的最大和
TCP/IP协议
Roguelike游戏成破解重灾区,如何破局?
sublime text中conda环境中plt.show无法弹出显示图片的问题
Double pointeur en langage C - - modèle classique
电脑清理,删除的系统文件
深度剖析C语言指针
角色动画(Character Animation)的现状与趋势
gcc动态库fPIC和fpic编译选项差异介绍
如何进行接口测试测?有哪些注意事项?保姆级解读
Is it safe to open an account in Zheshang futures?
Detailed explanation of heap sorting
Problems in loading and saving pytorch trained models
MySQL learning record 11jdbcstatement object, SQL injection problem and Preparedstatement object
China polyether amine Market Forecast and investment strategy report (2022 Edition)
LeetCode:387. 字符串中的第一个唯一字符
Process of obtaining the electronic version of academic qualifications of xuexin.com
移位运算符