剑指offer-37

题目:序列化二叉树

请实现两个函数,分别用来序列化和反序列化二叉树。
将树写入一个文件被称为“序列化”,读取文件后重建同样的二叉树被称为“反序列化”。

二叉树节点

1
2
3
4
5
6
7
8
9
10
11
private static class BinaryTreeNode {
private int val;
private BinaryTreeNode left;
private BinaryTreeNode right;

public BinaryTreeNode() {
}
public BinaryTreeNode(int val) {
this.val = val;
}
}

举例说明

二叉树

1
2
3
4
5
      1
/ \
2 3
/ / \
4 5 6

按前序遍历(只有前序遍历从根节点开始)系列化之后:

1
1,2,4,$,$,$,3,5,$,$,6,$,$,

思路

  • 以前的先序和后序遍历序列重构二叉树存在缺点:
  1. 要求二叉树中没有数值相同的结点
  2. 要求整个序列都读出后才能开始重构,如果序列是流式输入,那么就需要等待序列输出完毕才能完成二叉树的重构
  • 利用先序遍历
  1. node之间用,隔开
  2. 保存二叉树空结点为$
    利用这样的序列,就可以规避上面存在的两种缺点。

代码实现

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
69
70
71
72
73
74
75
76
77
78
79
80
import java.util.LinkedList;
import java.util.Queue;

public class _37{
private static class BinaryTreeNode {
private int value;
private BinaryTreeNode left;
private BinaryTreeNode right;

public BinaryTreeNode() {
}
public BinaryTreeNode(int value) {
this.value = value;
}
}


public static String serialize(BinaryTreeNode root) {
if (root == null) {
return "$,";
}
String res = root.value + ",";
res += serialize(root.left);
res += serialize(root.right);
return res;
}

public static BinaryTreeNode deserialize(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 deserialize(queue);
}

public static BinaryTreeNode deserialize(Queue<String> queue) {
String value = queue.poll();//移除并返问队列头部的元素(如果队列为空,返回null)
if (value.equals("$")) {
return null;
}//分别递归消费这个队列
BinaryTreeNode root = new BinaryTreeNode(Integer.valueOf(value));
root.left = deserialize(queue);
root.right = deserialize(queue);
return root;
}

public static void main(String[] args) {
// 1
// / \
// 2 3
// / / \
// 4 5 6
BinaryTreeNode n1 = new BinaryTreeNode(1);
BinaryTreeNode n2 = new BinaryTreeNode(2);
BinaryTreeNode n3 = new BinaryTreeNode(3);
BinaryTreeNode n4 = new BinaryTreeNode(4);
BinaryTreeNode n5 = new BinaryTreeNode(5);
BinaryTreeNode n6 = new BinaryTreeNode(6);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n3.left = n5;
n3.right = n6;

String result = serialize(n1);
System.out.println("serialize: "+result);
BinaryTreeNode root = deserialize(result) ;
System.out.println("deserialize: ");
printTree(root);
}

public static void printTree(BinaryTreeNode node) {
if (node != null) {
System.out.print(node.value + " ");
printTree(node.left);
printTree(node.right);
}
}
}

序列化二叉树

> >