LeetCode 331. 验证二叉树的前序序列化
题目描述
题意分析
前序序列依次记录根、左子树和右子树，空节点用
#占位。题目保证逗号分隔的每一项已经是合法整数或#，只需判断这些项能否组成完整的二叉树，并且不能重建树。
解法：槽位计数验证序列化
核心思路
[!blue]
把一个等待填写节点或
#的位置称为槽位，用slots记录尚未填写的槽位数量。初始只有根的位置，所以slots = 1。每读入一项，都先占用一个槽位：
- 整数表示真实节点，它还需要左右两个孩子的位置，因此消耗一个、新增两个，槽位净增 $1$。
#表示当前位置为空，不再产生孩子，槽位净减 $1$。按前序顺序，每一项都填入接下来应访问的槽位；真实节点新产生的左右位置，也按先左后右的顺序等待填写。只要还有槽位，下一项就有合法位置可放。因此验证时只需计数，不必保存每个位置属于哪个节点。
合法性需要同时满足两个条件：读取下一项前
slots > 0，否则树已经结束却还有多余内容；全部读完后slots == 0，否则还有孩子位置没有交代。两者一起保证每一项都能安放，且最终没有遗漏。只有#时，根位置恰好被填空，也是一棵合法的空树。
解题步骤
- 令
slots = 1，从字符串开头逐个 token 扫描。- 处理 token 前若
slots == 0，说明前面已经构成完整树，当前 token 无处可放，返回false。- token 为
#时令slots--；否则它是数字节点，令slots++，这已合并了「消耗一个、新增两个」。题目保证格式有效，检查 token 的第一个字符即可分辨这两种情况。- 向后扫描到下一个逗号或字符串末尾，整体跳过当前 token；外层循环再越过逗号，定位下一项，不创建分割数组。
- 所有 token 扫描完后，返回
slots == 0。
代码实现
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)$，只使用槽位计数和扫描下标，没有拆分字符串或建树。
关键点总结
[!green]
- 槽位表示待填充位置；实节点净增一个，
#净减一个。- 判据包含两部分：读 token 前不能无槽位，读完后不能有剩余槽位。
- 前序顺序保证 token 总是填入下一个槽位，因此一个计数器就能代替建树或栈模拟。
- 直接扫描到逗号可整体跳过 token，多位整数只计算一次，并把额外空间保持为 $O(1)$。
易错点总结
[!yellow]
- 只检查整数项与
#的总数量关系，无法发现前缀已经填满整棵树、后面却还有多余项的情况。- 少了结束时的
slots == 0，会接受孩子位置尚未全部填写的残缺序列。- 数字节点直接
slots += 2而忘了它自己也要消耗一个槽位；净变化应是+1。- 按数字字符逐个更新槽位，会把一个多位整数误算成多个节点；必须整体跳过当前 token。
- 将「槽位更新后为
0」立即判错：最后一个#本来就应让槽位归零；错误是归零后还有 token。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 297. 二叉树的序列化与反序列化 | 困难 | 序列化中的空位标记保留结构，本题只检查槽位能否被恰好消费，不实际建树。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！