LeetCode_二叉树_困难_297.二叉树的序列化与反序列化
2023-09-27 14:25:46 时间
1.题目
序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示:输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree
2.思路
(1)递归
3.代码实现(Java)
//思路1————递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
//定义特殊字符
String SEP = ",";
String NULL = "null";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder builder = new StringBuilder();
encodeTree(root, builder);
return builder.toString();
}
public void encodeTree(TreeNode root, StringBuilder builder) {
if (root == null) {
builder.append(NULL).append(SEP);
return;
}
//将当前根节点的节点值保存到 builder 中,并且使用逗号 "," 进行分隔
builder.append(root.val).append(SEP);
//递归遍历当前根节点的左右子树
encodeTree(root.left, builder);
encodeTree(root.right, builder);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
//将字符串转化为列表
LinkedList<String> nodes = new LinkedList<>();
for (String str : data.split(SEP)) {
nodes.addLast(str);
}
return decodeTree(nodes);
}
public TreeNode decodeTree(LinkedList<String> nodes) {
if (nodes.isEmpty()) {
return null;
}
/*
列表中的第一个节点就是根节点
removeFirst():删除链表中的第一个元素并将其返回
*/
String firstNode = nodes.removeFirst();
if (firstNode.equals(NULL)) {
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(firstNode));
//递归创建 root 的左右子树
root.left = decodeTree(nodes);
root.right = decodeTree(nodes);
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));
相关文章
- Leetcode: Perfect Squares
- Leetcode: Valid Parentheses
- LeetCode高频题:如何不用int转字符数组,实现int类型数字x的第L位和R位数字交换
- [LeetCode] Partition List
- [LeetCode]剑指 Offer 53 - II. 0~n-1中缺失的数字
- LeetCode 144. 二叉树的前序遍历
- LeetCode搜索二叉树的练习
- 【leetcode周赛记录】第80场双周赛记录
- leetcode 8 String to Integer (atoi)
- [LeetCode] 963. Minimum Area Rectangle II 面积最小的矩形之二
- [LeetCode] 919. Complete Binary Tree Inserter 完全二叉树插入器
- [LeetCode] Champagne Tower 香槟塔
- [LeetCode] Parse Lisp Expression 解析Lisp表达式
- [LeetCode] 654. Maximum Binary Tree 最大二叉树
- [LeetCode] 617. Merge Two Binary Trees 合并二叉树
- [LeetCode] Longest Harmonious Subsequence 最长和谐子序列
- [LeetCode] Binary Tree Tilt 二叉树的坡度
- [LeetCode] Shuffle an Array 数组洗牌
- [LeetCode] 297. Serialize and Deserialize Binary Tree 二叉树的序列化和去序列化
- [LeetCode] 94. Binary Tree Inorder Traversal 二叉树的中序遍历
- [LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历
- leetcode 94. Binary Tree Inorder Traversal 二叉树的中序遍历(中等)