二叉樹的序列化和反序列化尉咕。我一開始想用BFS的，但第一不知道怎么處理空子樹涤久，第二不知道怎么還原一棵樹。于是照著solutions的高票答案寫了一遍忍弛。
Approach 1 : preorder traverse（dfs）
1
/ \
2 3
/ \
4 5
對于上面這棵樹响迂，這種方法會把它serialize成"1,2,X,X,3,4,X,X,5,X,X,"這樣的字符串。也就是preorder地遍歷细疚。buildTree的過程也是遞歸蔗彤，跟serialize的過程其實就是相反的。遞歸構(gòu)造一棵樹的方法還是值得注意的惠昔。
private static final String spliter = ",";
private static final String NN = "X";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
preorder(root, sb);
return sb.toString();
}
private void preorder(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append(NN).append(spliter);
return;
}
sb.append(node.val).append(spliter);
preorder(node.left, sb);
preorder(node.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Queue<String> queue = new LinkedList<>();
queue.addAll(Arrays.asList(data.split(spliter)));
//如何返回root：遞歸返回的最終就是root
return buildTree(queue);
}
private TreeNode buildTree(Queue<String> queue) {
String val = queue.poll();
if (val.equals(NN)) {
return null;
}
TreeNode node = new TreeNode(Integer.valueOf(val));
node.left = buildTree(queue);
node.right = buildTree(queue);
return node;
}
問了同舉幕与，他讓我用Gson.toJson試一下。
Approach 2 : BFS
我先去看電影了镇防。
bfs的解法會把上面的tree序列化成："1 2 3 n n 4 5 n n n n "這樣。理解起來其實更容易潮饱。serialize的過程就是level order traverse的過程来氧，注意null的處理。build tree的過程是把null跳過不接到parent上香拉。
//BFS
public String serialize(TreeNode root) {
if (root == null) return "";
Queue<TreeNode> q = new LinkedList<>();
StringBuilder res = new StringBuilder();
q.add(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node == null) {
res.append("n ");
continue;
}
res.append(node.val + " ");
q.add(node.left);
q.add(node.right);
}
return res.toString();
}
public TreeNode deserialize(String data) {
if (data == "") return null;
Queue<TreeNode> q = new LinkedList<>();
String[] values = data.split(" ");
TreeNode root = new TreeNode(Integer.parseInt(values[0]));
q.add(root);
for (int i = 1; i < values.length; i++) {
TreeNode parent = q.poll();
if (!values[i].equals("n")) {
TreeNode left = new TreeNode(Integer.parseInt(values[i]));
parent.left = left;
q.add(left);
}
if (!values[++i].equals("n")) {
TreeNode right = new TreeNode(Integer.parseInt(values[i]));
parent.right = right;
q.add(right);
}
}
return root;
}
摘抄：
【注意】
1啦扬、不要幻想不用分隔符（我用的是“，”）凫碌，沒有分隔符對于1位以上的數(shù)是區(qū)分不了的扑毡。比如345，你覺得是1個數(shù)345還是分別3個數(shù)呢盛险？（這就是我愚蠢的地方瞄摊，耗費我數(shù)小時思考）
2、String的split方法有個坑：
對于"11,12,13,"苦掘，用data.split(",")可以得到正確結(jié)果换帜；但是",11,12,13"split后得到的是null。所以分隔符要放后面
這題還有個follow up:449. Serialize and Deserialize BST ,用這題的代碼也可以過鹤啡，但是沒用到BST的性質(zhì)惯驼。看了下那題的答案，不是很懂deserialization的過程祟牲。
ref：
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/#/solutions
http://www.reibang.com/p/18578f767668
http://blog.csdn.net/byamao1/article/details/53086548
