力扣——449. 序列化和反序列化二叉搜索树(Java、C代码实现)
2023-09-14 09:05:31 时间
- 序列化和反序列化二叉搜索树
序列化是将数据结构或对象转换为一系列位的过程,以便它可以存储在文件或内存缓冲区中,或通过网络连接链路传输,以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串,并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
示例 1:
输入:root = [2,1,3]
输出:[2,1,3]
示例 2:
输入:root = []
输出:[]
Java代码:
public class Codec {
public String serialize(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
postOrder(root, list);
String str = list.toString();
return str.substring(1, str.length() - 1);
}
public TreeNode deserialize(String data) {
if (data.isEmpty()) {
return null;
}
String[] arr = data.split(", ");
Deque<Integer> stack = new ArrayDeque<Integer>();
int length = arr.length;
for (int i = 0; i < length; i++) {
stack.push(Integer.parseInt(arr[i]));
}
return construct(Integer.MIN_VALUE, Integer.MAX_VALUE, stack);
}
private void postOrder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
postOrder(root.left, list);
postOrder(root.right, list);
list.add(root.val);
}
private TreeNode construct(int lower, int upper, Deque<Integer> stack) {
if (stack.isEmpty() || stack.peek() < lower || stack.peek() > upper) {
return null;
}
int val = stack.pop();
TreeNode root = new TreeNode(val);
root.right = construct(val, upper, stack);
root.left = construct(lower, val, stack);
return root;
}
}
C代码:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode *tree_node(int val) {
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
#define MAXN 10000
/* Generate the pre-order string.
Nodes are separated by '_'. */
void genstr(struct TreeNode *root, char **strp) {
if (root == NULL) {
return;
}
char buf[32];
sprintf(buf, "%d_", root->val);
strcat(*strp, buf);
genstr(root->left, strp);
genstr(root->right, strp);
}
/* Transfer the serialize string to integer array. */
int *get_vals(char *str, int *retsz) {
int n = strlen(str);
int *vals = (int *) malloc(MAXN * sizeof(int));
*retsz = 0;
char *cp = str;
for (int i = 0; i < n; i++) {
if (str[i] != '_')
continue;
str[i] = '\0';
vals[(*retsz)++] = atoi(cp);
cp = str + i + 1;
}
return vals;
}
/* Generate BST according to the pre-order values array. */
struct TreeNode *gentree(int *vals, int l, int r) {
if (l > r)
return NULL;
if (l == r)
return tree_node(vals[l]);
struct TreeNode *root = tree_node(vals[l]);
/* Find the index of the first value which
larger than [root->val] by binary search. */
int i = l + 1, j = r, mid, index = r + 1;
while (i <= j) {
mid = i + (j - i >> 1);
if (vals[mid] >= root->val) {
index = mid;
j = mid - 1;
} else {
i = mid + 1;
}
}
root->left = gentree(vals, l + 1, index - 1);
root->right = gentree(vals, index, r);
return root;
}
/** Encodes a tree to a single string. */
char *serialize(struct TreeNode *root) {
char *str = (char *) calloc(5 * MAXN + 1, 1);
genstr(root, &str);
return str;
}
/** Decodes your encoded data to tree. */
struct TreeNode *deserialize(char *data) {
int *vals, vals_size;
struct TreeNode *root;
vals = get_vals(data, &vals_size);
root = gentree(vals, 0, vals_size - 1);
free(vals);
return root;
}
// Your functions will be called as such:
// char* data = serialize(root);
// deserialize(data);
作者:KJ.JK
本文仅用于交流学习,未经作者允许,禁止转载,更勿做其他用途,违者必究。
文章对你有所帮助的话,欢迎给个赞或者 star,你的支持是对作者最大的鼓励,不足之处可以在评论区多多指正,交流学习
相关文章
- java局域网发送文件_Java如何实现局域网文件传输代码案例分享
- java用什么软件_Java编程什么软件最好用?
- java除法保留两位小数_JAVA除法保留小数点后两位的两种方法
- java 登录 qq_Java实现QQ登录
- java启动器_JAVA基础:Java 启动器如何查找类
- java编程软件下载_Ee Java(Java编程软件) V1.1.0 官方版
- java冒泡排序经典代码_Java 8大经典排序算法(含源代码),必须收藏!
- java heap space 什么意思_java heap space是什么意思?
- Java 中的三大特性(超详细篇)
- MySQL字段类型如何转为java_Java JDBC中,MySQL字段类型到JAVA类型的转换
- java webservice 实例_Java WebService 简单实例(附实例代码)
- java网页安全提示_win7系统打开网页提示“应用程序已被JAVA安全阻止”的解决方法…
- java冒泡排序代码_Java冒泡排序
- Java入门代码_java编程自学网
- Java map转实体类_java实体类转json
- JAVA代码审计之java反序列化
- 反编译Java_java反编译的代码可以修改么
- JAVA程序员简历模板_Java工程师简历模板
- java.security.cert.CertPathValidatorException: Path does not chain with any of the trust anchors详解数据库
- Java中的HashMap和HashTable到底哪不同详解编程语言
- 解决Java程序连接MySQL数据库的方法(java链接mysql数据库)
- 代码Linux下编写Java代码的指南(linux编写java)
- 新手进阶:从Java开发到Linux系统架构(java转linux)
- 构建Java应用程序中Redis集群的方法(java连redis集群)
- 在Linux环境下轻松搭建Java开发环境(linux下搭建java)
- Java程序如何在Linux上顺利部署?快来了解一下!(java部署到Linux)
- 版本Linux查看Java版本的简单方法(linux 查看java)
- Java和Redis的配合安装方法(java redis安装)
- Java中Oracle使用实践(java中oracle题)
- 缓存使用Redis让Java代码更加迅速缓存设置(redis设置java)
- Java线程模型缺陷