二叉树的序列化和反序列化。我一开始想用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的过程其实就是相反的。递归构造一棵树的方法还是值得注意的。
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位以上的数是区分不了的。比如345,你觉得是1个数345还是分别3个数呢?(这就是我愚蠢的地方,耗费我数小时思考)
2、String的split方法有个坑:
对于"11,12,13,",用data.split(",")可以得到正确结果;但是",11,12,13"split后得到的是null。所以分隔符要放后面
这题还有个follow up:449. Serialize and Deserialize BST ,用这题的代码也可以过,但是没用到BST的性质。看了下那题的答案,不是很懂deserialization的过程。
ref:
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/#/solutions
http://www.jianshu.com/p/18578f767668
http://blog.csdn.net/byamao1/article/details/53086548