LeetCode 331. 验证二叉树的前序序列化
目录
题目描述
题意分析
给一个用逗号分隔的字符串，它声称是某棵二叉树按前序遍历写出来的序列化结果，其中每个空指针被显式写成
#。要判断这个字符串是否真的可能来自某棵二叉树，返回布尔值。注意题目只要求「判断」，不要求还原出那棵树，也不需要指出错在哪个位置。这个信号很重要：只要能找到一个必须成立的数量关系，就不必真的把树建出来。
「空指针被显式写出来」是解题的全部前提。正因为每个空位都占了一个 token，序列里的信息才是完备的——如果省略
#，同一个字符串可能对应多棵树，题目根本无从判断。输入本身的合法性题目已经保证：token 要么是
#，要么是一个不含逗号的整数，不会出现空 token、多余逗号或非法字符。所以不需要写任何字符级的格式校验，只用关心结构。但整数可能是多位数（比如"12"），逐字符扫描时必须把一个数字整体当成一个 token。需要识别的非法情形其实有两类：一类是「早停」，前面的节点还没安置完序列就把位置填满了，后面的 token 无处可放，比如
"9,#,#,1"；另一类是「没写完」，序列结束时还有空指针没被交代，比如"9,#"。任何只覆盖其中一类的判断都不完整。边界上最小的合法输入是单个
"#"，代表一棵空树，必须返回true；很多写法会在这个用例上翻车。
解法：槽位计数验证序列化
核心思路
题目只要求判断结构是否合法，无需真正建树。把「等待被 token 填充的孩子位置」记为槽位：开始只有根槽位，所以
slots = 1。每个 token 都先占用一个槽位；数字节点再产生左右两个槽位，净变化为
+1；#不产生新槽位，净变化为-1。循环不变量是：处理当前 token 前，
slots恰好是已见前缀创建、但尚未填充的槽位数。因此读取 token 前slots必须大于0，否则树已完整却还有多余内容；全部读完后slots必须等于0，否则还有孩子位置未交代。这两个条件也足以保证正确性：前序顺序使每个 token 总是填入下一个待用槽位；若过程中槽位从未提前耗尽，且结束时恰好耗尽，所有 token 就恰好组成一棵完整二叉树的序列化。
解题步骤
- 令
slots = 1，从字符串开头逐个 token 扫描。- 处理 token 前若
slots == 0，说明前面已经构成完整树，当前 token 无处可放，返回false。- token 以
#开头时令slots--；否则它是数字节点，令slots++，这已合并了「消耗一个、新增两个」。- 向后走到下一个逗号，从而整体跳过多位数或负数 token，不创建分割数组。
- 所有 token 扫描完后，返回
slots == 0。例如
"9,#,#"的槽位变化为1 -> 2 -> 1 -> 0，合法；"9,#"结束时还剩一个槽位，而"#,#"在读第二个 token 前槽位已归零，两者都不合法。
代码实现
class Solution {
public boolean isValidSerialization(String preorder) {
int slots = 1;
int n = preorder.length();
for (int i = 0; i < n; i++) {
if (slots == 0) {
return false;
}
slots += preorder.charAt(i) == '#' ? -1 : 1;
while (i < n && preorder.charAt(i) != ',') {
i++;
}
}
return slots == 0;
}
}
func isValidSerialization(preorder string) bool {
slots := 1
for i := 0; i < len(preorder); i++ {
if slots == 0 {
return false
}
if preorder[i] == '#' {
slots--
} else {
slots++
}
for i < len(preorder) && preorder[i] != ',' {
i++
}
}
return slots == 0
}
复杂度分析
- 时间复杂度：$O(n)$，
n为序列化字符串长度；外层定位 token，内层跳到逗号，每个字符只被常数次访问。- 空间复杂度：$O(1)$，只使用槽位计数和扫描下标，没有拆分字符串或建树。
关键点总结
- 槽位表示待填充位置；实节点净增一个，
#净减一个。- 判据包含两部分：读 token 前不能无槽位，读完后不能有剩余槽位。
- 前序顺序保证 token 总是填入下一个槽位，因此一个计数器就能代替建树或栈模拟。
- 直接扫描到逗号可整体跳过 token，既兼容多位数和负数，又把额外空间降为 $O(1)$。
易错点总结
- 只在结束时比较 token 总数：
"#,9,#"的数量关系正确，但根槽位早已被第一个#耗尽，序列仍不合法。- 少了结束时的
slots == 0："9,#"会被误判为合法，实际上右孩子槽位尚未填充。- 数字节点直接
slots += 2而忘了它自己也要消耗一个槽位；净变化应是+1。- 按字符而非 token 更新槽位：
"12,#,#"中的12只是一个节点，负号也不是独立节点。- 将「槽位更新后为
0」立即判错：最后一个#本来就应让槽位归零；错误是归零后还有 token。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 20. 有效的括号 | 简单 | 同样是「过程不能穿底、结尾必须归零」，但有三种括号需配对，计数器不够 |
| 32. 最长有效括号 | 困难 | 从判断是否合法升级为求最长合法段，需要记录穿底位置而非只判真假 |
| 105. 从前序与中序遍历序列构造二叉树 | 中等 | 没有 # 占位，必须靠中序切分左右子树，真的要把树建出来 |
| 144. 二叉树的前序遍历 | 简单 | 反向练习：从树生成序列，理解本题输入是怎么产生的 |
| 297. 二叉树的序列化与反序列化 | 困难 | 要求真正实现序列化与还原，本题的「暴力递归解析」正是它的一半 |
| 1249. 移除无效的括号 | 中等 | 不止判断合法性，还要给出删除方案，需要记下穿底与残留的具体下标 |