题目描述
请实现两个函数，分别用来序列化和反序列化二叉树
解法一：（存在问题）
根据“重建二叉树”的启发，我们可以通过记录下二叉树的前序遍历和中序遍历（或后序遍历和中序遍历），然后通过两个遍历序列来反序列化二叉树。
public class Solution {
int i = 0;
//序列化二叉树
String Serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
PreOrder(root, sb);
sb.append("|");
InfixOrder(root, sb);
return sb.toString();
}
//求前序遍历
void PreOrder(TreeNode root, StringBuilder sb) {
if(root == null) {
return;
}
sb.append(root.val);
sb.append(",");
PreOrder(root.left, sb);
PreOrder(root.right, sb);
}
//求中序遍历
void InfixOrder(TreeNode root, StringBuilder sb) {
if(root == null) {
return;
}
InfixOrder(root.left, sb);
sb.append(root.val);
sb.append(",");
InfixOrder(root.right, sb);
}
//反序列化二叉树
TreeNode Deserialize(String str) {
int index = str.indexOf("|");
String[] preOrder = str.substring(0, index).split(",");
String[] infixOrder = str.substring(index + 1, str.length()).split(",");
return DeserializeCore(preOrder, infixOrder, 0, preOrder.length - 1);
}
TreeNode DeserializeCore(String[] preOrder, String[] infixOrder, int start, int end) {
if (end - start < 0) {
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(preOrder[i]));
int index = 0;
for(index = start; index <= end; index++) {
if(infixOrder[index].equals(preOrder[i])) {
break;
}
}
i++;
root.left = DeserializeCore(preOrder, infixOrder, start, index - 1);
root.right = DeserializeCore(preOrder, infixOrder, index + 1, end);
return root;
}
}
在序列化二叉树的时候一定要加入分隔符，如果直接序列化成Sting|String，如12345|53214的格式，无法解决多位数字的问题，如当节点为12时则会出问题。
同时这个算法存在致命缺点：
1、该方法要求二叉树中不能有数值重复的节点
2、只有当两个序列中的所有数据都读出后才能开始反序列化。如果两个遍历序列的数据是从一个 流里读出来的，那么可能需要较长的时间。
解法二：
之所以前序遍历无法完成反序列化是因为无法很好地处理空节点问题，我们只需要将空节点序列化为特殊字符如#即可。同时，这种反序列化在得到根节点的数值后便可以开始了，无需等待所有数据接收完毕才能开始。
public class Solution {
StringBuilder sb = new StringBuilder();
String s = null;
String Serialize(TreeNode root) {
if(root == null) {
sb.append("#" + ",");
return null;
}
sb.append(root.val + ",");
Serialize(root.left);
Serialize(root.right);
return sb.toString();
}
TreeNode Deserialize(String str) {
if(s == null) {
s = str;
}
//考虑空节点
if(s == null || s.length() <= 0)
return null;
int index = s.indexOf(",");
TreeNode root = null;
String number = s.substring(0, index);
s = s.substring(index + 1);
if(!number.equals("#")) {
int n = Integer.parseInt(number);
root = new TreeNode(n);
TreeNode left = Deserialize(s);
root.left = left;
TreeNode right = Deserialize(s);
root.right = right;
}
return root;
}
}
通过判断序列是否为空来决定反序列化是否终止。
当然也可以通过设置一个计数器来顺序遍历序列，当遍历到最后的的两个空节点时递归停止（序列化序列最后两个必定为空节点）。
public class Solution {
StringBuilder sb = new StringBuilder();
int index = -1;
String Serialize(TreeNode root) {
if(root == null) {
sb.append("#" + ",");
return null;
}
sb.append(root.val + ",");
Serialize(root.left);
Serialize(root.right);
return sb.toString();
}
TreeNode Deserialize(String str) {
index++;
if(str == null)
return null;
String[] strr = str.split(",");
TreeNode root = null;
if(!strr[index].equals("#")) {
int n = Integer.valueOf(strr[index]);
root = new TreeNode(n);
root.left = Deserialize(str);
root.right = Deserialize(str);
}
return root;
}
}
解法三：
既然前序遍历考虑空节点可以完成序列化与反序列化，则层序遍历也可以。
public class Solution {
//序列化二叉树，按层遍历
String Serialize(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
StringBuilder sb = new StringBuilder();
if(root == null) {
return null;
}
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if(node == null) {
sb.append("#" + ",");
}
else {
sb.append(node.val + ",");
queue.add(node.left);
queue.add(node.right);
}
}
return sb.toString();
}
//反序列化二叉树
TreeNode Deserialize(String str) {
if(str == null || str.length() == 0) {
return null;
}
int index = 0;
String[] list = str.split(",");
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(list[index++]));
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if(list[index].equals("#")) {
node.left = null;
}
else {
node.left = new TreeNode(Integer.parseInt(list[index]));
queue.add(node.left);
}
index++;
if(list[index].equals("#")) {
node.right = null;
}
else {
node.right = new TreeNode(Integer.parseInt(list[index]));
queue.add(node.right);
}
index++;
}
return root;
}
}
按层遍历二叉树一般需要借助队列。
PS：
当判断字符串是否等于“#”时切记使用equals而不是==。参见“Java 中 == 和 equals的区别”
