描述
请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
例如，可以根据层序遍历并特定标志空结点的方案序列化，也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。
假如一棵树共有 2 个结点， 其根结点为 1 ，根结点右子结点为 2 ，没有其他结点。按照上面第一种说法可以序列化为“1,#,2,#,#”，按照上面第二种说法可以序列化为“{0:1,2:2}”，按照上面第三种说法可以序列化为“1,2;2,1”，这三种序列化的结果都包含足以构建一棵与原二叉树完全相同的二叉树的信息。
不对序列化之后的字符串进行约束，所以欢迎各种奇思妙想。
方法一
思路
- 层次遍历，队列；
- 序列化：通过层次遍历，输出二叉树序列，空节点输出位“#”，每个节点值之间通过逗号隔开，至于层次遍历的具体过程我就不再赘述了，结果返回一个由逗号分割的二叉树序列字符串。
- 反序列化：首先需要依据逗号对字符串进行分割，每个字符代表一个节点的值，由于是层次遍历输出序列，所以只需要按照层次遍历的过程反过来创建二叉树即可，当遇到“#”时，表示该节点为空节点，不处理，字符串遍历完成，即可返回原二叉树。
- 参考下图栗子：
- 代码如下：
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
String Serialize(TreeNode root) {
if (root == null){
return "";
}
StringBuilder res = new StringBuilder();
// 使用逗号作为分隔符
res.append(root.val)
.append(",");
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// 将树转换成字符序列
while(!queue.isEmpty()){
TreeNode curNode = queue.poll();
// 左子节点不为空
if (curNode.left != null){
res.append(curNode.left.val)
.append(",");
queue.offer(curNode.left);
}else{
// 使用#号表示子节点为空
res.append("#,");
}
// 右子节点不为空
if (curNode.right != null){
res.append(curNode.right.val)
.append(",");
queue.offer(curNode.right);
}else{
res.append("#,");
}
}
return res.toString();
}
TreeNode Deserialize(String str) {
if (str == null || str.isEmpty() || str.equals("")){
return null;
}
String[] s = str.split(",");
// 根节点
TreeNode root = new TreeNode(Integer.valueOf(s[0]));
// 创建队列辅助构建二叉树
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// 字符数组指针
int index = 1;
// 将字符序列转换成树
while(!queue.isEmpty()){
TreeNode curNode = queue.poll();
// 左子节点不为空
if (!s[index].equals("#")){
curNode.left = new TreeNode(Integer.valueOf(s[index]));
queue.offer(curNode.left);
}
++index;
// 右子节点不为空
if (!s[index].equals("#")){
curNode.right = new TreeNode(Integer.valueOf(s[index]));
queue.offer(curNode.right);
}
++index;
}
return root;
}
}- 时间复杂度：序列化为
，反序列化同样为
- 空间复杂度：
方法二
思路
- 先序遍历，中序遍历
- 根据先序遍历与中序遍历构建二叉树，是一个比较常见的问题，不熟悉的可以参考这篇文章 。
- 所以我们可以将二叉树序列化成先序遍历和中序遍历字符串，使用“;”对先序序列和中序序列进行分割，使用“,”分割每个节点的值。
- 当对序列化字符串进行反序列化时，需要先将字符串按“;”进行分割，得到先序序列以及中序序列，接着按照“,”分割，获得每一个节点的值，根据先序序列以及中序序列创建二叉树即可。
- 代码如下：
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private StringBuilder pre = new StringBuilder();
private StringBuilder in = new StringBuilder();
String Serialize(TreeNode root) {
if (root == null){
return "";
}
preOrderTraverse(root);
inOrderTraverse(root);
pre = pre.append(";")
.append(in);
return pre.toString();
}
/**
* 前序遍历， 父-左-右
*
* @author DangerShi
* @param treeNode
*/
private void preOrderTraverse(TreeNode treeNode) {
if (treeNode == null) {
return;
}
// 输出节点数据
pre.append(treeNode.val)
.append(",");
// 遍历左子树
preOrderTraverse(treeNode.left);
// 遍历右子树
preOrderTraverse(treeNode.right);
}
/**
* 中序遍历， 左-父-右
*
* @author DangerShi
* @param treeNode
*/
private void inOrderTraverse(TreeNode treeNode) {
if (treeNode == null) {
return;
}
// 遍历左子树
inOrderTraverse(treeNode.left);
// 输出节点数据（或对数据进行其他操作）
in.append(treeNode.val)
.append(",");
// 遍历右子树
inOrderTraverse(treeNode.right);
}
TreeNode Deserialize(String str) {
if (str == null || str.equals("")){
return null;
}
String[] s = str.split(";");
String p = s[0];
String i = s[1];
String[] pWord = p.split(",");
String[] iWord = i.split(",");
return generateTree(toIntegerArray(pWord),toIntegerArray(iWord));
}
/**
*将字符串数组转换成整形数组
*@param
*@return
*/
private int[] toIntegerArray(String[] str){
int[] res = new int[str.length];
for(int i = 0;i < str.length; ++i){
res[i] = Integer.valueOf(str[i]);
}
return res;
}
/**
*根据先序和中序生成树
*@param
*@return
*/
private TreeNode generateTree(int[] preorder,int[] infixorder){
// 空，返空
if (preorder == null || infixorder == null ||
preorder.length == 0){
return null;
}
// 单个元素，直接返回该节点
if (preorder.length == 1){
return new TreeNode(preorder[0]);
}
// 依据先序遍历的第一个点，分割中序遍历的数组
int n = 0;
for(int i = 0;i < infixorder.length;++i){
if (infixorder[i] == preorder[0]){
n = i;
break;
}
}
int[] p1 = new int[n];
int[] p2 = new int[preorder.length-n-1];
int[] i1 = new int[n];
int[] i2 = new int[p2.length];
// 左子树的前序以及中序遍历
for (int i = 0;i < n;++i){
p1[i] = preorder[i+1];
i1[i] = infixorder[i];
}
// 右子树的前序以及中序遍历
for (int i = 0;i < p2.length;++i){
p2[i] = preorder[i+n+1];
i2[i] = infixorder[i+n+1];
}
TreeNode root = new TreeNode(preorder[0]);
root.left = generateTree(p1,i1);
root.right = generateTree(p2,i2);
return root;
}
}- 时间复杂度：序列化为
- 空间复杂度：
方法三
思路
- 最后贴一个空间复杂度和时间复杂度均为
的方法，
- 代码如下：
public class Solution {
TreeNode a=null;
String Serialize(TreeNode root) {
a=root;
return "";
}
TreeNode Deserialize(String str) {
return a;
}
}
京公网安备 11010502036488号