遍歷BFSDFS 二叉樹的序列化與反序列化
題目
難度：困難
序列化是將一個(gè)數(shù)據(jù)結(jié)構(gòu)或者對象轉(zhuǎn)換為連續(xù)的比特位的操作，進(jìn)而可以將轉(zhuǎn)換后的數(shù)據(jù)存儲在一個(gè)文件或者內(nèi)存中，同時(shí)也可以通過網(wǎng)絡(luò)傳輸?shù)搅硪粋€(gè)計(jì)算機(jī)環(huán)境，采取相反方式重構(gòu)得到原數(shù)據(jù)。
請?jiān)O(shè)計(jì)一個(gè)算法來實(shí)現(xiàn)二叉樹的序列化與反序列化。這里不限定你的序列 / 反序列化算法執(zhí)行邏輯，你只需要保證一個(gè)二叉樹可以被序列化為一個(gè)字符串并且將這個(gè)字符串反序列化為原始的樹結(jié)構(gòu)。
示例:
你可以將以下二叉樹：
1
/ \
2 3
/ \
4 5
序列化為 "[1,2,3,null,null,4,5]"解法一：dfs解法
深度優(yōu)先搜索算法（Depth First Search，簡稱DFS）
1.解題
序列化：求二叉樹的先序遍歷序列 反序列化：通過序列化得到的先序遍歷序列 構(gòu)建原二叉樹
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder res=mySeri(root,new StringBuilder());
return res.toString();
}
StringBuilder mySeri(TreeNode root,StringBuilder sb){
if(root==null){
sb.append("null,");
return sb;
}
else if(root!=null){
sb.append(root.val);
sb.append(",");
mySeri(root.left,sb);
mySeri(root.right,sb);
}
return sb;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String []temp=data.split(","); // 將序列化的結(jié)果轉(zhuǎn)為字符串?dāng)?shù)組
List<String> list=new LinkedList<>(Arrays.asList(temp)); // 字符串?dāng)?shù)組轉(zhuǎn)為集合類 便于操作
return myDeSeri(list);
}
public TreeNode myDeSeri(List<String> list){
TreeNode root;
if(list.get(0).equals("null")){
list.remove(0); // 刪除第一個(gè)元素 則第二個(gè)元素成為新的首部 便于遞歸
return null;
}
else{
root=new TreeNode(Integer.valueOf(list.get(0)));
list.remove(0);
root.left=myDeSeri(list);
root.right=myDeSeri(list);
}
return root;
}
}2.方法解釋
1.spilt(); 拆分String為字符串?dāng)?shù)組 2.Arrays.asList();
（1）該方法不適用于基本數(shù)據(jù)類型（byte,short,int,long,float,double,boolean） （2）該方法將數(shù)組與列表鏈接起來，當(dāng)更新其中之一時(shí)，另一個(gè)自動更新 （3）不支持add和remove方法 （1）該方法不適用于基本數(shù)據(jù)類型（byte,short,int,long,float,double,boolean） ?。?）該方法將數(shù)組與列表鏈接起來，當(dāng)更新其中之一時(shí)，另一個(gè)自動更新 ?。?）不支持add和remove方法
解法二：bfs解法
BFS，其英文全稱是Breadth First Search。 寬度優(yōu)先搜索算法（又稱廣度優(yōu)先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。
1.解法
序列化：通用bfs 反序列化：每次遍歷2個(gè)節(jié)點(diǎn) 這2個(gè)節(jié)點(diǎn)是出隊(duì)節(jié)點(diǎn)的左右孩子
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root==null){
return "";
}
StringBuilder res=new StringBuilder();
Queue<TreeNode> queue=new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode cur=queue.poll();
if(cur==null){
res.append("null,");
}
else{
res.append(String.valueOf(cur.val));
res.append(",");
queue.offer(cur.left);
queue.offer(cur.right);
}
}
return res.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.equals("")){
return null;
}
String []temp=data.split(",");
TreeNode root=new TreeNode(Integer.valueOf(temp[0]));
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
TreeNode cur=root;
for(int i=1;i<temp.length;){
cur=queue.poll();
if(!temp[i].equals("null")){
cur.left=new TreeNode(Integer.valueOf(temp[i]));
queue.offer(cur.left);
}
i+=1;
if(!temp[i].equals("null")){
cur.right=new TreeNode(Integer.valueOf(temp[i]));
queue.offer(cur.right);
}
i+=1;
}
return root;
}
}
2.方法解析
1.offer(); 往隊(duì)列尾部插入元素，如果超出邊界則返回false
深度優(yōu)先與廣度優(yōu)先的差異
稀疏圖bfs會快于dfs，稠密圖差不多。dfs寫比較簡單，bfs沒有棧溢出風(fēng)險(xiǎn)
1.DFS：棧（先進(jìn)后出） 走到盡頭 步驟：
1.首先A入棧，
2、A出棧時(shí)，A的鄰接結(jié)點(diǎn)B，C相應(yīng)入棧 （這里假設(shè)C在下，B在上）
3.B出棧時(shí)，B的鄰接結(jié)點(diǎn)A，C，D中未進(jìn)過棧的D入棧
4.D出棧時(shí)，D的鄰接結(jié)點(diǎn)B，C，E，F(xiàn)中未進(jìn)過棧的E、F入棧（假設(shè)E在下，F(xiàn)在上）
5.F出棧時(shí)，F(xiàn)沒有鄰接結(jié)點(diǎn)可入棧
6.E出棧，E的鄰接結(jié)點(diǎn)C，D已入過棧
7.C出棧
2.BFS： 隊(duì)列（先進(jìn)先出） 按照層次來遍歷 步驟：
1.首先A入隊(duì)列，
2.A出隊(duì)列時(shí)，A的鄰接結(jié)點(diǎn)B，C相應(yīng)進(jìn)入隊(duì)列
3.B出隊(duì)列時(shí)，B的鄰接結(jié)點(diǎn)A，C，D中未進(jìn)過隊(duì)列的D進(jìn)入隊(duì)列
4.C出隊(duì)列時(shí)，C的鄰接結(jié)點(diǎn)A，B，D，E中未進(jìn)過隊(duì)列的E進(jìn)入隊(duì)列
5.D出隊(duì)列時(shí)，D的鄰接結(jié)點(diǎn)B，C，E，F(xiàn)中未進(jìn)過隊(duì)列的F進(jìn)入隊(duì)列
6.E出隊(duì)列，沒有結(jié)點(diǎn)可再進(jìn)隊(duì)列
7.F出隊(duì)列
更多建議：