二叉树的序列化和反序列化
作者：Grey
原文地址：
题目链接见：LeetCode 297. Serialize and Deserialize Binary Tree
主要思路
可以用如下三种方式
第一种方式，先序遍历生成序列化字符串，然后按先序规则再反序列化；
第二种方式，后序遍历生成序列化字符串，然后按后序规则再反序列化；
第三种方式，按层遍历生成序列化字符串，然后按层次规则再反序列化。
注：这里不能用中序方式序列化和反序列化，因为，如果二叉树是如下两棵
两棵树的中序遍历结果都是[null,a,a,a,null]，这样进行反序列化的时候，就无法区分这两棵树了。
其次，针对任何一棵二叉树，我们需要将一些空的节点补充完整，比如下述二叉树
其中 b 的左孩子，c 的左孩子，d 的右孩子，都是空节点，我们可以用 null 来表示，但是不能忽略，所以以按层序列化为例，我们将空节点设置为‘#’字符，并用'[]'框住序列化的字符串，然后用逗号分隔节点，所以，上述二叉树
按层序列化的结果是[a,b,c,#,d,#,e,f,#]
代码如下
// 二叉树按层遍历经典实现。
public static String serialize(TreeNode head) {
if (head == null) {
return "[]";
}
StringBuilder sb = new StringBuilder("[");
Queue queue = new LinkedList<>();
queue.offer(head);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
sb.append(node == null ? "#" : String.valueOf(node.val)).append(",");
if (node != null) {
queue.offer(node.left);
queue.offer(node.right);
}
}
sb.append("]");
return sb.toString();
}
反序列化的方式就是把上述字符串还原成一个二叉树，使用一个队列即可，代码如下：
// 按层反序列化
public static TreeNode deserialize(String data) {
if ("[]".equals(data)) {
return null;
}
data = data.substring(1, data.length() - 2);
String[] values = data.split(",");
TreeNode head = new TreeNode(Integer.valueOf(values[0]));
Queue queue = new LinkedList<>();
queue.offer(head);
int size = 1;
while (!queue.isEmpty() && size < values.length) {
TreeNode c = queue.poll();
c.left = "#".equals(values[size]) ? null : new TreeNode(Integer.valueOf(values[size]));
size++;
if (size < values.length) {
c.right = "#".equals(values[size]) ? null : new TreeNode(Integer.valueOf(values[size]));
size++;
}
if (c.left != null) {
queue.offer(c.left);
}
if (c.right != null) {
queue.offer(c.right);
}
}
return head;
}
先序序列化/反序列化，后序序列化/反序列化方法类似
// 后序方式序列化 迭代方法
public static String serialize3(TreeNode head) {
if (head == null) {
return "[]";
}
// 后序遍历的结果加入栈（可以用递归也可以用迭代）
Stack stack1 = new Stack<>();
Stack stack2 = new Stack<>();
stack1.push(head);
while (!stack1.isEmpty()) {
TreeNode c = stack1.pop();
stack2.push(c);
if (c != null) {
stack1.push(c.left);
stack1.push(c.right);
}
}
// 栈->字符串
StringBuilder sb = new StringBuilder("[");
while (!stack2.isEmpty()) {
TreeNode node = stack2.pop();
sb.append(node == null ? "#" : node.val).append(",");
}
sb.append("]");
return sb.toString();
}
// 后序方式反序列化 迭代方式
public static TreeNode deserialize3(String data) {
if ("[]".equals(data)) {
return null;
}
String[] values = data.substring(1, data.length() - 2).split(",");
Stack stack = new Stack<>();
for (String value : values) {
stack.push(value);
}
return posDerial(stack);
}
private static TreeNode posDerial(Stack stack) {
String s = stack.pop();
if ("#".equals(s)) {
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(s));
root.right = posDerial(stack);
root.left = posDerial(stack);
return root;
}
// 先序方式序列化 迭代做法
// 头 左 右
public static String serialize2(TreeNode head) {
if (head == null) {
return "[]";
}
StringBuilder sb = new StringBuilder("[");
Stack queue = new Stack<>();
queue.push(head);
while (!queue.isEmpty()) {
TreeNode c = queue.pop();
sb.append(c == null ? "#" : c.val).append(",");
if (c != null) {
queue.push(c.right);
queue.push(c.left);
}
}
sb.append("]");
return sb.toString();
}
// 先序反序列化
public static TreeNode deserialize2(String data) {
if ("[]".equals(data)) {
return null;
}
String[] values = data.substring(1, data.length() - 2).split(",");
Queue queue = new LinkedList<>();
for (String value : values) {
queue.offer("#".equals(value) ? null : new TreeNode(Integer.valueOf(value)));
}
return preDesrial(queue);
}
private static TreeNode preDesrial(Queue queue) {
TreeNode node = queue.poll();
if (node == null) {
return null;
}
node.left = preDesrial(queue);
node.right = preDesrial(queue);
return node;
}