請(qǐng)實(shí)現(xiàn)兩個(gè)函數(shù)，分別用來序列化和反序列化2叉樹
甚么是序列化？
可以理解為1直存儲(chǔ)結(jié)構(gòu)
序列化后還要可以反序列化
對(duì)樹的序列號(hào)，可以理解為層次遍歷，但是也要記錄其中的空結(jié)點(diǎn)，這是為了能夠回去
我們知道可以從前序遍歷和中序遍歷構(gòu)造出1棵2叉樹。受此啟發(fā)，我們可以先把1棵2叉樹序列化成1個(gè)前序遍歷序列和1個(gè)中序序列，然后再反序列化時(shí)通過這兩個(gè)序列重構(gòu)出原2叉樹。
這個(gè)思路有兩個(gè)缺點(diǎn)。1個(gè)缺點(diǎn)是該方法要求2叉樹中不能用有數(shù)值重復(fù)的結(jié)點(diǎn)。另外只有當(dāng)兩個(gè)序列中所有數(shù)據(jù)都讀出后才能開始反序列化。如果兩個(gè)遍歷序列的數(shù)據(jù)是從1個(gè)流里讀出來的，那便可能需要等較長的時(shí)間。
實(shí)際上如果2叉樹的序列化是從根結(jié)點(diǎn)開始的話，那末相應(yīng)的反序列化在根結(jié)點(diǎn)的數(shù)值讀出來的時(shí)候就能夠開始了。因此我們可以根據(jù)前序遍歷的順序來序列化2叉樹，由于前序遍歷是從根結(jié)點(diǎn)開始的。當(dāng)在遍歷2叉樹碰到 NULL 指針時(shí)，這些 NULL 指針序列化成1個(gè)特殊的字符（比如‘#’）。另外，結(jié)點(diǎn)的數(shù)值之間要用1個(gè)特殊字符（比如’,’）隔開。
public class Solution {
String Serialize(TreeNode root) {
if(root == null)
return "";
StringBuilder sb = new StringBuilder();
Serialize(root, sb);
return sb.toString();
}
void Serialize(TreeNode root, StringBuilder sb) {
if(root == null) {
sb.append("#,");
return;
}
sb.append(root.val);
sb.append(',');
Serialize(root.left, sb);
Serialize(root.right, sb);
}
int index = -1;
TreeNode Deserialize(String str) {
if(str.length() == 0)
return null;
String[] strs = str.split(",");
return Deserialize(strs);
}
TreeNode Deserialize(String[] strs) {
index++;
if(!strs[index].equals("#")) {
TreeNode root = new TreeNode(0);
root.val = Integer.parseInt(strs[index]);
root.left = Deserialize(strs);
root.right = Deserialize(strs);
return root;
}
return null;
}
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
