请实现两个函数，分别用来序列化和反序列化二叉树
序列化二叉树
http://www.nowcoder.com/questionTerminal/cf7e25aa97c04cc1a68c8f040e71fb84
请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
String Serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
if(root != null){
//双端队列
Deque<TreeNode> queue = new LinkedList();
queue.offer(root);
while(queue.size() > 0){
TreeNode treeNode = queue.pop();
if(treeNode == null){
sb.append("#");
}else{
//这里一定要将val专为char字符，否则如果val是57,1259,多位数会被保存为多个字符，57会被切割为'5'和'7'
sb.append((char)treeNode.val);
queue.offer(treeNode.left);
queue.offer(treeNode.right);
}
}
}
return sb.toString();
}
TreeNode Deserialize(String str) {
TreeNode root = null;
if(str != null && str.length()>0){
root = new TreeNode((int)str.charAt(0));
}
Deque<TreeNode> queue = new LinkedList();
queue.offer(root);
int i = 1;
// 这里要判断一下i因为如果str在最后表示是最后一层的节点
while(queue.size() > 0 && i < str.length()-2){
TreeNode treeNode = queue.pop();
if(str.charAt(i) != '#'){
// str.charAt(i)转为int其值为unicode编码的数值
TreeNode leftNode = new TreeNode(str.charAt(i));
queue.offer(leftNode);
treeNode.left = leftNode;
}
i++;
if(str.charAt(i) != '#'){
TreeNode rightNode = new TreeNode(str.charAt(i));
queue.offer(rightNode);
treeNode.right = rightNode;
}
i++;
}
return root;
}
} 
投递牛客等公司10个岗位 >