【Offer】[37] 【序列化二叉树】
2024-09-01 06:21:45
题目描述
请实现两个函数，分别用来序列化和反序列化二叉树。
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ! 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
思路分析
利用前序遍历的序列，要将二叉树想象成一颗满二叉树，其中空节点要用#表示，节点之间用!分隔。
测试用例
- 功能测试：输入的二叉树是完全二叉树;所有节点都没有左/右子树的二叉树;只有一个节点的二叉树。
- 特殊输入测试：指向二叉树根节点的指针为nullptr指针。
Java代码
public class Offer37 {
public static void main(String[] args) {
test1();
test2();
test3();
}
String Serialize(TreeNode root) {
StringBuffer sb = new StringBuffer();
if (root == null) {
sb.append("#!");
} else {
sb.append(root.val + "!");
sb.append(Serialize(root.left));
sb.append(Serialize(root.right));
}
return sb.toString();
}
int index = 0;
TreeNode Deserialize(String str) {
TreeNode node = null;
int start = index;
while (str.charAt(index) != '!') {
index++;
}
if (!str.substring(start, index).equals("#")) {
node = new TreeNode(Integer.parseInt(str.substring(start, index)));
index++;
node.left = Deserialize(str);
node.right = Deserialize(str);
} else {
index++;
}
return node;
}
private static void test1() {
}
private static void test2() {
}
private static void test3() {
}
}
代码链接
最新文章
- http://www.cnblogs.com/kissdodog/p/4159176.html
- linux大文件分割 split命令
- C# 如何在Excel 动态生成PivotTable
- SQL各种连接查询详解(左连接、右连接..)
- 【转】object标签和embed标签
- C# Eval在asp.net中的用法及作用
- Matalab之模糊KMeans实现
- APUE学习--网络编程(3)
- CCLayer在Touch事件(Standard Touch Delegate和Targeted Touch Delegate)
- hdu 1542 Atlantis（求矩形面积并）
- webview h5页面 关闭
- css初始化值
- iOS开发——导入第三方库引起的unknown type name 'NSString'
- java源码学习（三）Enum
- Windows下编译nginx-rtmp-module
- 终极解决方案：java.security.cert.CertificateException: Certificates does not conform to algorithm constraints
- SAC E#1 - 一道难题 Tree
- Boyer-Moore算法
- 用7ch中断例程完成jmp near ptr s指令的功能，用bx向中断例程传送转移位移。
- 对TextFile格式文件的lzo压缩建立index索引