题目描述：
给出一个二叉树的前序遍历序列，如果是一个空节点使用#替代。验证是否是一个合法的遍历序列。
数据范围：
$1 \le preorder.length \le 10^4$
题解：
首先统一的做法是缩点，先把叶子结点缩点（后面跟着两个#的），用#替换这个叶子结点。一直缩到不能缩为止，如果最后剩余一个空根节点说明合法。
其次可以发现空节点的数量是比节点数量多1，因为每次加一个节点时都是消耗一个空节点，增加两个空节点，净增 $1$ 。因此可以根据空节点的数量判断是否合法。初始空节点数量为 $1$ 。然后每次遇到一个非空节点，先减后加；每次遇到一个空节点减减。如果中途有小于 $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
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
bool isValidSerialization(string preorder)
{
int cnt = 1, n = preorder.size();
for (int i = 0; i < n; ++i)
{
if (preorder[i] == '#')
{
if(cnt == 0) return false;
--cnt;
++i;
}
else if (isdigit(preorder[i]))
{
if(cnt == 0) return false;
cnt++;
while (i < n && preorder[i] != ',')
++i;
}
}
return cnt == 0;
}
};
|