面试题37：序列化二叉树
题目要求：
实现两个函数，分别用来序列化和反序列化二叉树。
解题思路：
此题能让人想到重建二叉树。但二叉树序列化为前序遍历序列和中序遍历序列，然后反序列化为二叉树的思路在本题有两个关键缺点：1.全部数据都读取完才能进行反序列化。2.该方法需要保证树中节点的值各不相同（本题无法保证）。
其实，在遍历结果中，记录null指针后（比如用一个特殊字符$），那么任何一种遍历方式都能回推出原二叉树。但是如果期望边读取序列化数据，边反序列化二叉树，那么仅可以使用前序或层序遍历。但层序记录的null个数要远多于前序，因此选择使用记录null指针的前序遍历进行序列化。
package chapter4;
import structure.TreeNode;
/**
* Created by ryder on 2017/7/19.
* 序列化二叉树
*/
public class P194_SerializeBinaryTrees {
public static String serialize(TreeNode<Integer> root){
if(root==null)
return "$,";
StringBuilder result = new StringBuilder();
result.append(root.val);
result.append(",");
result.append(serialize(root.left));
result.append(serialize(root.right));
return result.toString();
}
public static TreeNode<Integer> deserialize(String str){
StringBuilder stringBuilder = new StringBuilder(str);
return deserializeCore(stringBuilder);
}
public static TreeNode<Integer> deserializeCore(StringBuilder stringBuilder){
if(stringBuilder.length()==0)
return null;
String num = stringBuilder.substring(0,stringBuilder.indexOf(","));
stringBuilder.delete(0,stringBuilder.indexOf(","));
stringBuilder.deleteCharAt(0);
if(num.equals("$"))
return null;
TreeNode<Integer> node = new TreeNode<>(Integer.parseInt(num));
node.left = deserializeCore(stringBuilder);
node.right = deserializeCore(stringBuilder);
return node;
}
public static void main(String[] args){
// 1
// / \
// 2 3
// / / \
// 4 5 6
// 1,2,4,$,$,$,3,5,$,$,6,$,$
TreeNode<Integer> root = new TreeNode<Integer>(1);
root.left = new TreeNode<Integer>(2);
root.right = new TreeNode<Integer>(3);
root.left.left = new TreeNode<Integer>(4);
root.right.left = new TreeNode<Integer>(5);
root.right.right = new TreeNode<Integer>(6);
System.out.println("原始树："+root);
String result = serialize(root);
System.out.println("序列化结果："+result);
TreeNode<Integer> deserializeRoot = deserialize(result);
System.out.println("反序列后的树："+deserializeRoot);
}
}
运行结果
原始树：[1,2,3,4,5,6]
序列化结果：1,2,4,$,$,$,3,5,$,$,6,$,$,
反序列后的树：[1,2,3,4,5,6]
