05 August 2008
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
class Codec {
// Encodes a tree to a single string.
public String serialize(Node root) {
List<String> list=new LinkedList<>();
serializeHelper(root,list);
return String.join(",",list);
}
private void serializeHelper(Node root, List<String> list){
if(root==null){
return;
}else{
list.add(String.valueOf(root.val));
list.add(String.valueOf(root.children.size()));
for(Node child:root.children){
serializeHelper(child,list);
}
}
}
// Decodes your encoded data to tree.
public Node deserialize(String data) {
if(data.isEmpty())
return null;
String[] ss=data.split(",");
Queue<String> q=new LinkedList<>(Arrays.asList(ss));
return deserializeHelper(q);
}
private Node deserializeHelper(Queue<String> q){
Node root=new Node();
root.val=Integer.parseInt(q.poll());
int size=Integer.parseInt(q.poll());
root.children=new ArrayList<Node>(size);
for(int i=0;i<size;i++){
root.children.add(deserializeHelper(q));
}
return root;
}
}
BFS
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
43
44
45
46
47
class Codec {
// Encodes a tree to a single string.
public String serialize(Node root) {
if (root == null) {
return "";
}
StringBuilder sb = new StringBuilder();
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
sb.append(root.val).append(",").append(root.children.size()).append(",");
while (!queue.isEmpty()) {
Node cur = queue.poll();
for (Node node : cur.children) {
queue.offer(node);
sb.append(node.val).append(",").append(node.children.size()).append(",");
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public Node deserialize(String data) {
if (data.length() == 0) {
return null;
}
String[] nodes = data.split(",");
Queue<Node> queue = new LinkedList<Node>();
Queue<Integer> childQueue = new LinkedList<Integer>();
Node root = new Node(Integer.valueOf(nodes[0]));
queue.offer(root);
childQueue.offer(Integer.valueOf(nodes[1]));
int i = 2;
while (!queue.isEmpty()) {
Node cur = queue.poll();
cur.children = new ArrayList<>();
int n = childQueue.poll();
for (int j = 0; j < n; j++) {
Node child = new Node(Integer.valueOf(nodes[i++]));
childQueue.offer(Integer.valueOf(nodes[i++]));
queue.offer(child);
cur.children.add(child);
}
}
return root;
}
}