描述：
設(shè)計一個算法秒旋，并編寫代碼來序列化和反序列化二叉樹。將樹寫入一個文件被稱為“序列化”诀拭，讀取文件后重建同樣的二叉樹被稱為“反序列化”迁筛。
如何反序列化或序列化二叉樹是沒有限制的，你只需要確备ぃ可以將二叉樹序列化為一個字符串细卧，并且可以將字符串反序列化為原來的樹結(jié)構(gòu)尉桩。
給出一個測試數(shù)據(jù)樣例， 二叉樹{3,9,20,#,#,15,7}贪庙，表示如下的樹結(jié)構(gòu)：
3
/
9 20
/
15 7
我們的數(shù)據(jù)是進行BFS遍歷得到的蜘犁。當(dāng)你測試結(jié)果wrong answer時，你可以作為輸入調(diào)試你的代碼止邮。
你可以采用其他的方法進行序列化和反序列化这橙。
講解：
對于這個題我把樹結(jié)構(gòu)序列化為 3，9农尖，20析恋，15，7盛卡≈恚空節(jié)點用#來表示。
序列化過程：
public String serialize(TreeNode root) {
if (root == null) return "";
//將所有的節(jié)點放入list中滑沧，包括null節(jié)點
ArrayList<TreeNode> list = new ArrayList<>();
list.add(root);
for (int i = 0; i < list.size(); i++){
TreeNode q = list.get(i);
if (q == null){
continue;
}
list.add(q.left);
list.add(q.right);
}
//去除尾部的null節(jié)點
while (list.get(list.size()-1)==null){
list.remove(list.size()-1);
}
//使用StringBuilder鏈接起來
StringBuilder sb = new StringBuilder();
sb.append(list.get(0).val);
for (int i = 1; i < list.size(); i++){
TreeNode node = list.get(i);
if (node != null){
sb.append(",");
sb.append(node.val);
} else {
sb.append(",#");
}
}
return sb.toString();
}
反序列過程：
if (data == ""){
return null;
}
String[] vals = data.split(",");
ArrayList<TreeNode> queue = new ArrayList<>();
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
queue.add(root);
int index = 0; //標(biāo)記父節(jié)點但的位置
boolean isLeftChild = true; //判斷是否為左子樹并村，沒鏈接一個節(jié)點就取反一次
for (int i = 1; i < vals.length; i++){
if (!vals[i].equals("#")){
TreeNode node = new TreeNode(Integer.parseInt(vals[i]));
if (isLeftChild){
queue.get(index).left = node;
} else {
queue.get(index).right = node;
}
queue.add(node);
}
if (!isLeftChild){
index++;
}
isLeftChild = !isLeftChild;
}
return root;
}
