题目
结果
代码
一个非空的节点必须要有两个子节点，根据这个关系，可以得出一个基于“期望节点数”算法：
- 遇到数字 父节点的期望节点数减一，当前节点的期望节点数置为二。
- 遇到空节点， 只需将父节点的期望节点数减一
最后判断所有节点的期望节点数是否为0，这个过程可以用栈很好的模拟。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func isValidSerialization(preorder string) bool {
s := strings.Split(preorder, ",")
stk := []int{1}
for _, v := range s {
if len(stk) == 0 {
return false
}
stk[len(stk)-1]--
if stk[len(stk)-1] == 0 {
stk = stk[:len(stk)-1]
}
if unicode.IsDigit(str2rune(v)) {
stk = append(stk, 2)
}
}
return len(stk) == 0
}
func str2rune(s string) rune {
return rune(s[0])
}
|
复杂度
时间复杂度：O（n）
空间复杂度：O（n）