题解 | #序列化二叉树#
序列化二叉树
http://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84
参考别人的代码，层序遍历，用!做分割，用#代表空指针，这里的层序遍历空指针也要遍历进去。
/*，
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();
Queue<TreeNode> queue=new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int len=queue.size();
for(int i=0;i<len;i++)
{
TreeNode tmp=queue.poll();
if(tmp!=null){ //与一般的层序遍历不一样，这里把空指针也放进去了
sb.append(String.valueOf(tmp.val)+"!");
queue.add(tmp.left);
queue.add(tmp.right);
}
else{
sb.append("#!"); //用！分割，用#代替null
}
}
}
return sb.toString();
}
TreeNode Deserialize(String str) {
int n=str.length();
Queue<TreeNode> queue=new LinkedList<>();
Queue<String> q=new LinkedList<>();
String[]s=str.split("!");
for(int i=0;i<s.length;i++){
q.add(s[i]);
}
String rootVal=q.poll();
if(rootVal.equals("#")){
return null;
}
TreeNode root=new TreeNode(Integer.parseInt(rootVal));
queue.add(root);
while(!queue.isEmpty()){
int len=queue.size();
for(int i=0;i<len;i++){
TreeNode tmp=queue.poll();
String leftVal=q.poll();
String rightVal=q.poll();
TreeNode treeNodeL=leftVal.equals("#")?null:new TreeNode(Integer.parseInt(leftVal));
TreeNode treeNodeR=rightVal.equals("#")?null:new TreeNode(Integer.parseInt(rightVal));
tmp.left=treeNodeL;
tmp.right=treeNodeR;
if(treeNodeL!=null){
queue.add(treeNodeL);
}
if(treeNodeR!=null){
queue.add(treeNodeR);
}
}
}
return root;
}
}