本文首發(fā)于我的個(gè)人博客：尾尾部落
題目描述
請(qǐng)實(shí)現(xiàn)兩個(gè)函數(shù)，分別用來序列化和反序列化二叉樹
解題思路
- 對(duì)于序列化：使用前序遍歷，遞歸的將二叉樹的值轉(zhuǎn)化為字符版仔，并且在每次二叉樹的結(jié)點(diǎn)不為空時(shí)钝凶，在轉(zhuǎn)化val所得的字符之后添加一個(gè)','作為分割; 對(duì)于空節(jié)點(diǎn)則以 '#,' 代替。
- 對(duì)于反序列化：將字符串按照“甫何，”進(jìn)行分割出吹，插入到隊(duì)列中，然后依次從隊(duì)列中取出字符建立節(jié)點(diǎn)辙喂，遞歸創(chuàng)建一個(gè)二叉樹捶牢。
參考代碼
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
String Serialize(TreeNode root) {
if(root == null){
return "#,";
}
StringBuffer res = new StringBuffer(root.val + ",");
res.append(Serialize(root.left));
res.append(Serialize(root.right));
return res.toString();
}
TreeNode Deserialize(String str) {
String [] res = str.split(",");
Queue<String> queue = new LinkedList<String>();
for(int i = 0; i < res.length; i++){
queue.offer(res[i]);
}
return pre(queue);
}
TreeNode pre(Queue<String> queue){
String val = queue.poll();
if(val.equals("#"))
return null;
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = pre(queue);
node.right = pre(queue);
return node;
}
}
