看了左程云老师的算法课，记录学习过程，整理思路和形成系统认识。
题目：二叉树序列化和反序列化（算法课第五课）
二叉树被记录成文件的过程叫做二叉树的序列化，通过文件内容重建原来的二叉树的过程叫做二叉树的反序列化。
#表示这个节点为空，节点值不存在，_(后面代码用！)表示一个值的结束
image
分析
树结构
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
前序遍历序列化
public static String serialByPre(Node head) {
if (head == null) {
return "#!";
}
String res = head.value + "!";
res += serialByPre(head.left);
res += serialByPre(head.right);
return res;
}
前序遍历反序列化
把结果字符串str变成字符串类型的数组，记为values,数组代表一棵二叉树先序遍历的节点顺序。
- 分割
- 还原数组
- 按照先序顺序还原
例如：
str="12!3!#!#!#!",生成的values为‘12’，‘3’，‘#’，‘#’，‘#’，然后用values[0..4]按照先序遍历的顺序建立整棵树。
1，遇到“12”，生成节点值12的节点（head） 然后用values[1..4]建立节点12的左子树
2，遇到‘3’,生成节点值为3的节点，它是节点12的左孩子，然后用values[2..4]建立节点3的左子树
3，遇到‘#’，生成null节点，它是节点3的左孩子，该节点为null，所以这个节点没有后续建立子树过程。回到节点3后，用values[3..4]建立节点3的右子树
4，遇到“#”生成null节点，它是节点3的右孩子，该节点为null，所以这个节点没有后续建立子树过程。回到节点3后，再回到节点1，用values[4]建立节点1的右子树。
5，遇到“#”，生成null节点，它是节点1的右孩子，该节点为null，所以这个节点没有后续建立子树过程。整个过程结束。
总的代码
import java.util.LinkedList;
import java.util.Queue;
public class SerializeAndReconstructTree {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static String serialByPre(Node head) {//序列化
if (head == null) {
return "#!";
}
String res = head.value + "!";
res += serialByPre(head.left);//左子树递归 消费
res += serialByPre(head.right);
return res;
}
public static Node reconByPreString(String preStr) {
String[] values = preStr.split("!");
Queue<String> queue = new LinkedList<String>();
for (int i = 0; i != values.length; i++) {
queue.offer(values[i]);
}
return reconPreOrder(queue);
}
public static Node reconPreOrder(Queue<String> queue) {
String value = queue.poll();
if (value.equals("#")) {
return null;
}
Node head = new Node(Integer.valueOf(value));
head.left = reconPreOrder(queue);
head.right = reconPreOrder(queue);
return head;
}
public static void main(String[] args) {
// 10
// / \
// 20 30
// / / \
// 40 50 60
Node head = new Node(10);
head.left = new Node(20);
head.left.left = new Node(40);
head.right = new Node(30);
head.right.left = new Node(50);
head.right.right = new Node(60);
String res = serialByPre(head);
System.out.println(res);
System.out.println(head.value==reconByPreString(res).value);
}
}
输出：
10!20!40!#!#!#!30!50!#!#!60!#!#!
true
