Depth First Search (DFS)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Codec {
public String serializeUtil(TreeNode root, String str) {// Recursive serialization.
if (root == null) {
str += "null,";
} else {
str += str.valueOf(root.val) + ","+serializeUtil(root.left, str)+serializeUtil(root.right, str);
}
return str;
}
public String serialize(TreeNode root) {// Encodes a tree to a single string.
return serializeUtil(root, "");
}
public TreeNode deserializeUtil(List<String> l) {// Recursive deserialization.
if (l.get(0).equals("null")) {
l.remove(0);
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(l.get(0)));
l.remove(0);
root.left = deserializeUtil(l);
root.right = deserializeUtil(l);
return root;
}
public TreeNode deserialize(String data) {// Decodes your encoded data to tree.
String[] data_array = data.split(",");
List<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
return deserializeUtil(data_list);
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
link
BFS1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41class Codec {
public String serialize(TreeNode root) {
if (root == null) return "";
Queue<TreeNode> q = new LinkedList<>();
StringBuilder res = new StringBuilder();
q.offer(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node == null) {
res.append("NULL,");
continue;
}
res.append(node.val + ",");
q.offer(node.left);
q.offer(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.offer(root);
for (int i = 1; i < values.length; i++) {
TreeNode parent = q.poll();
if (!values[i].equals("NULL")) {
TreeNode left = new TreeNode(Integer.parseInt(values[i]));
parent.left = left;
q.offer(left);
}
if (!values[++i].equals("NULL")) {
TreeNode right = new TreeNode(Integer.parseInt(values[i]));
parent.right = right;
q.offer(right);
}
}
return root;
}
}