题目
请实现两个函数,分别用来序列化和反序列化二叉树
解题
什么是序列化?
可以理解为一直存储结构
序列化后还要可以反序列化
对于树的序列号,可以理解为层次遍历,但是也要记录其中的空结点,这是为了能够回去
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution3 {
public String Serialize(TreeNode root) {
if(root == null)
return "";
StringBuilder sb = new StringBuilder();
Serialize(root, sb);
return sb.toString();
}
private void Serialize(TreeNode root, StringBuilder sb) {
if(root == null) {
sb.append("#,");
return;
}
sb.append(root.val);
sb.append(',');
Serialize(root.left, sb);
Serialize(root.right, sb);
}
int index = -1;
public TreeNode Deserialize(String str) {
if(str.length() == 0)
return null;
String[] strs = str.split(",");
return Deserialize(strs);
}
private TreeNode Deserialize(String[] strs) {
index++;
if(!strs[index].equals("#")) {
TreeNode root = new TreeNode(0);
root.val = Integer.parseInt(strs[index]);
root.left = Deserialize(strs);
root.right = Deserialize(strs);
return root;
}
return null;
}
public static void main(String[] args) {
Solution3 s3 = new Solution3();
/**
* 构造二叉树
* 1
* / \
* 2 3
* / \ / \
* 4 5 6 7
*/
TreeNode root = new TreeNode(1);
TreeNode left = new TreeNode(2);
TreeNode right = new TreeNode(3);
TreeNode left_1 = new TreeNode(4);
TreeNode right_1 = new TreeNode(5);
TreeNode right_2 = new TreeNode(6);
TreeNode left_2 = new TreeNode(7);
left.left = left_1;
left.right = right_1;
right.left = left_2;
right.right = right_2;
root.left = left;
root.right = right;
//System.out.println(s3.Serialize(root));//输出:1,2,4,#,#,5,#,#,3,7,#,#,6,#,#,
System.out.println(s3.Deserialize("1,2,4,#,#,5,#,#,3,7,#,#,6,#,#,").left.val);//输出:2
}
}