0331. Verify Preorder Serialization of a Binary Tree¶
题目信息¶
- 题号:
0331
- 难度:
Medium
- 主题:
二叉树序列化、先序顺序、空节点标记、完整消费
- 原题:
- 重点:
#表示空孩子、每个非空节点必须有两个孩子位置、序列不能缺项或含多余项
题目重述¶
给定字符串 preorder,它由逗号分隔的标记组成,表示一棵二叉树的先序序列化。普通整数标记表示非空节点,# 表示空节点;序列按“当前节点、左子树、右子树”的顺序记录。
判断整个字符串能否恰好描述一棵二叉树。所有标记必须被完整使用:既不能在某个非空节点的孩子位置尚未补齐时提前结束,也不能在一棵完整树已经结束后还有多余标记。preorder 长度位于 [1, 10^4],节点值位于 [0, 100],标记之间由单个逗号分隔且没有空格。无需真正构造树。
自建示例¶
只有根节点的完整树:
输入:preorder = "7,#,#"
输出:true
解释:7 是根节点,后面两个 # 分别完整表示它的左、右空孩子。
完整树后还有多余节点:
输入:preorder = "7,#,#,8"
输出:false
解释:前三个标记已经描述完一棵树,末尾的 8 没有可挂接的位置。
空树序列:
输入:preorder = "#"
输出:true
解释:单个空节点标记可以完整表示一棵空树。
用可用孩子槽位验证先序结构¶
开始时整棵树只有一个根槽位。读取一个标记就消耗一个槽位;若标记是非空节点,它会新增两个孩子槽位,若标记是 # 则不新增。任何时刻槽位变成负数,说明出现了没有父节点可以接纳的多余标记;读完整个序列后槽位必须恰好为零,才能说明没有缺失孩子或尾部多余标记。
这个计数不需要解析整数值,也不需要真正创建树。空树的特殊情况已经由第一个 # 消耗根槽位并结束;而 7,#,#,8 在前三个标记后槽位已经为零,读取 8 时立即判定非法。
C++ 实现¶
class Solution {
public:
bool isValidSerialization(std::string preorder) {
int slots = 1;
std::stringstream input(preorder);
std::string token;
while (std::getline(input, token, ',')) {
if (slots == 0) return false;
--slots;
if (token != "#") slots += 2;
}
return slots == 0;
}
};
代码分析¶
槽位是先序遍历下“结构是否还能接收节点”的压缩表示:非空节点消耗一个位置并产生两个子位置,空节点只消耗位置。检查顺序同时覆盖过早结束、非法前缀和多余标记三类错误。每个标记只参与一次解析,时间复杂度为 O(|preorder|),额外空间为 ``O(|preorder|)``(分割流和当前标记)。