二叉树的序列化和反序列化

二叉树被记录成文件的过程，叫做二叉树的序列化，通过文件内容重建原来二叉树的过程叫做二叉树的反序列化。
给定一棵二叉树的头节点head，并已知二叉树节点值的类型为32位整型。
请设计一种二叉树序列化和反序列化的方案并用代码实现。

应用：判断两颗二叉树中是否有子树完全相同，先序列化为文件，然后kmp

思路

将每个树的节点的值放在字符串中，用一个分隔符分开来，不然会引起歧义，然后将空节点也用特殊符号代替
本题用!代表分隔符，用#表示空结点
思路就是先序遍历和层次遍历，注意处理过程稍有不同

先序序列化及反序列化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 先序序列化
//类似于树的先序遍历
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> preQueue = new LinkedList<String>();
	for (int i = 0; i < values.length; i++) {
		preQueue.add(values[i]);
	}
	//还原树
	return reconPreOrder(preQueue);
}
//还原树的过程类似于树的先序遍历
public static Node reconPreOrder(Queue<String> queue) {
	//得到队头结点
	String string = queue.poll();
	if(string.equals("#")){
		return null;
	}
	//处理根节点
	Node head = new Node(Integer.valueOf(string));
	//处理左右节点
	head.left = reconPreOrder(queue);
	head.right = reconPreOrder(queue);
	return head;
}

层次序列化及反序列化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// 层次序列化
public static String serialByLevel(Node head) {
	if (head == null) {
		return "#!";
	}
	Queue<Node> queue = new LinkedList<Node>();
	// 头结点入队处理，而不出队时处理
	// 因为这里对于空节点也要处理
	String res = Integer.valueOf(head.value) + "!";
	queue.add(head);
	while (!queue.isEmpty()) {
		Node node = queue.poll();
		// 入队时处理左右节点，因为有空节点
		if (node.left != null) {
			res += Integer.valueOf(node.left.value) + "!";
			queue.add(node.left);
		} else {
			// 空结点也要处理
			res += "#!";
		}
		if (node.right != null) {
			res += Integer.valueOf(node.right.value) + "!";
			queue.add(node.right);
		} else {
			res += "#!";
		}
	}
	return res;
}
public static Node reconByLevelString(String levelStr) {
	
	String[] strings = levelStr.split("!");
	//与层次遍历相似
	Queue<Node> queue = new LinkedList<Node>();
	int index = 0;
	//处理头结点并入队
	Node head = generateNodeByString(strings[index++]);
	//不空才入队
	if(head != null){
		queue.add(head);
	}
	while(!queue.isEmpty()){
		//出队头
		Node node = queue.poll();
		//处理左结点，并入队
		node.left = generateNodeByString(strings[index++]);
		if(node.left != null){
			queue.add(node.left);
		}
		//处理右结点，并入队
		node.right = generateNodeByString(strings[index++]);
		if(node.right != null){
			queue.add(node.right);
		}
	}
	return head;
}
// 根据value返回node
public static Node generateNodeByString(String val) {
	if (val.equals("#")) {
		return null;
	}
	return new Node(Integer.valueOf(val));
}