序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
1
2
3
4
5
6
7
| _9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
|
例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
示例 1:
1
2
| 输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true
|
示例 2:
示例 3:
方法一：递归
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
| class Solution {
private int i = 0;
public boolean isValidSerialization(String preorder) {
String[] arr = preorder.split(",");
return helper(arr) && i == arr.length - 1;
}
private boolean helper(String[] arr){
int len = arr.length;
if(arr[i].equals("#")){
return i == arr.length - 1;
}
if(!arr[i].equals("#") && i + 2 < len
&& arr[i + 1].equals("#") && arr[i + 2].equals("#")){
i += 2;
return true;
}
if(i + 2 >= len){
return false;
}
boolean left = false, right = false;
i += 1;
if(arr[i].equals("#")){
left = true;
}else{
left = helper(arr);
}
if(!left){
return false;
}
i += 1;
if(arr[i].equals("#")){
right = true;
}else{
right = helper(arr);
}
return right;
}
}
|
方法二：栈
我们定义一个概念叫做槽位，一个槽位可被看作当前二叉树中正在等待被节点填充的那些位置。
每当遇到一个结点时：
- 遇到空结点，消耗一个槽位；
- 遇到非空结点，消耗一个槽位，增加两个子节点的槽位。
此外还需要对根节点进行处理。
我们使用栈来维护槽位的变化，栈中的每个元素代表了对应节点处剩余槽位的数量，栈顶元素代表下一步可用的槽位。每当遇到空结点时，仅将栈顶元素减 1 ，遇到非空节点时，将栈顶元素减 1 后，再向栈中压入一个 2 。无论何时，如果栈顶元素变为 0，立刻将栈顶弹出。结束后，如果栈为空，则序列合法，在遍历过程中，如果槽位数量不足，则序列不合法。
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
| class Solution {
public boolean isValidSerialization(String preorder) {
int n = preorder.length();
int i = 0;
Deque<Integer> stack = new LinkedList();
stack.push(1);
while(i < n){
if(stack.isEmpty()){
return false;
}
if(preorder.charAt(i) == ','){
i++;
} else if(preorder.charAt(i) == '#'){
int top = stack.pop() - 1;
if(top > 0){
stack.push(top);
}
i++;
} else{
while(i < n && preorder.charAt(i) != ','){
++i;
}
int top = stack.pop() - 1;
if(top > 0){
stack.push(top);
}
stack.push(2);
}
}
return stack.isEmpty();
}
}
|
方法三：计数
如果将方法二中栈中元素看成一个整体，即所有剩余槽位的数量，也能维护槽位的变化。因此我们只用维护一个计数器，代表栈中所有元素之和。
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
| class Solution {
public boolean isValidSerialization(String preorder) {
int n = preorder.length();
int i = 0;
int slots = 1;
while(i < n){
if(slots == 0){
return false;
}
if(preorder.charAt(i) == ','){
i++;
} else if(preorder.charAt(i) == '#'){
slots--;
i++;
} else{
while(i < n && preorder.charAt(i) != ','){
++i;
}
slots++;
}
}
return slots == 0;
}
}
|