0331. Verify Preorder Serialization of a Binary Tree ==================================================== 题目信息 -------- :题号: 0331 :难度: Medium :主题: 二叉树序列化、先序顺序、空节点标记、完整消费 :原题: `LeetCode 0331 `_ :重点: ``#`` 表示空孩子、每个非空节点必须有两个孩子位置、序列不能缺项或含多余项 题目重述 -------- 给定字符串 ``preorder``,它由逗号分隔的标记组成,表示一棵二叉树的先序序列化。普通整数标记表示非空节点,``#`` 表示空节点;序列按“当前节点、左子树、右子树”的顺序记录。 判断整个字符串能否恰好描述一棵二叉树。所有标记必须被完整使用:既不能在某个非空节点的孩子位置尚未补齐时提前结束,也不能在一棵完整树已经结束后还有多余标记。``preorder`` 长度位于 ``[1, 10^4]``,节点值位于 ``[0, 100]``,标记之间由单个逗号分隔且没有空格。无需真正构造树。 自建示例 -------- 只有根节点的完整树: .. code-block:: text 输入:preorder = "7,#,#" 输出:true 解释:7 是根节点,后面两个 # 分别完整表示它的左、右空孩子。 完整树后还有多余节点: .. code-block:: text 输入:preorder = "7,#,#,8" 输出:false 解释:前三个标记已经描述完一棵树,末尾的 8 没有可挂接的位置。 空树序列: .. code-block:: text 输入:preorder = "#" 输出:true 解释:单个空节点标记可以完整表示一棵空树。 用可用孩子槽位验证先序结构 ---------------------------- 开始时整棵树只有一个根槽位。读取一个标记就消耗一个槽位;若标记是非空节点,它会新增两个孩子槽位,若标记是 ``#`` 则不新增。任何时刻槽位变成负数,说明出现了没有父节点可以接纳的多余标记;读完整个序列后槽位必须恰好为零,才能说明没有缺失孩子或尾部多余标记。 这个计数不需要解析整数值,也不需要真正创建树。空树的特殊情况已经由第一个 ``#`` 消耗根槽位并结束;而 ``7,#,#,8`` 在前三个标记后槽位已经为零,读取 ``8`` 时立即判定非法。 C++ 实现 -------- .. code-block:: cpp 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|)``(分割流和当前标记)。