-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathCodecNary.java
More file actions
106 lines (96 loc) · 3.14 KB
/
CodecNary.java
File metadata and controls
106 lines (96 loc) · 3.14 KB
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import java.util.*;
class Node{
int val;
List<Node> children;
public Node(){}
public Node(int _val, List<Node> _children){
val = _val;
children = _children;
}
}
public class CodecNary {
/*
Serialize 3-ary tree:
1
/ | \
3 2 4
/ \
5 6
ie: as 1 [3 [5 6 ]2 4 ]
* */
/*
感觉自己越来越熟能生巧了，感觉自己inspired by se & de binary tree 和 calculator系列
serialize : 变形的pre-order traverse root [child child child ..]
deserialize: 还是利用int[] index 和括号一起做recursion，返回list of node
* */
public static void main(String[] args){
Node root = new Node(1, new ArrayList<>());
Node n3 = new Node(3, new ArrayList<>());
n3.children.add(new Node(5, new ArrayList<>()));
n3.children.add(new Node(6, new ArrayList<>()));
root.children.add(n3);
root.children.add(new Node(2, new ArrayList<>()));
root.children.add(new Node(4, new ArrayList<>()));
CodecNary obj = new CodecNary();
String data = obj.serialize(root);
System.out.println(data);
Node newRoot = obj.deserialize(data);
System.out.println(obj.serialize(newRoot));
}
public String serialize(Node root){
if(root == null){
return " ";
}
if(root.children == null || root.children.size() == 0){
return root.val + " ";
}
StringBuilder sb = new StringBuilder();
sb.append(root.val + " ");
sb.append("[");
for(Node child : root.children){
sb.append(serialize(child));
}
sb.append("]");
return sb.toString();
}
public Node deserialize(String data){
int[] index = {0};
List<Node> res = helper(data, index);
return res.get(0);
}
private List<Node> helper(String data, int[] index){
Stack<Node> stack = new Stack<>();
for(; index[0] < data.length()-1; index[0] ++){
char c = data.charAt(index[0]);
// find a number
if(Character.isDigit(c)){
int sum = 0;
while(index[0] < data.length()-1 && Character.isDigit(data.charAt(index[0]))){
sum = sum * 10 + (data.charAt(index[0])-'0');
index[0] ++;
}
Node cur = new Node(sum, new ArrayList<>());
stack.push(cur);
index[0] --;
}else if(c == '['){
index[0] ++;
List<Node> children = helper(data, index);
Node parent = stack.peek();
parent.children = children;
}else if (c == ']'){
List<Node> res = new ArrayList<>();
while(!stack.isEmpty()){
res.add(0, stack.pop());
}
return res;
}else{
continue;
}
}
List<Node> res = new ArrayList<>();
while(!stack.isEmpty()){
res.add(0, stack.pop());
}
return res;
}
}