[TOC] ## 题目描述 题目leetcode331地址：https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/ 序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。 ``` _9_ / \ 3 2 / \ / \ 4 1 # 6 / \ / \ / \ # # # # # # ``` 例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。 给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。 你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。 示例 1: ``` 输入: "9,3,4,#,#,1,#,#,2,#,6,#,#" 输出: true ``` ## 解题 ### 方法一，填充槽位 二叉树的建立也伴随着槽位数量的变化。每当遇到一个节点时： * 如果遇到了空节点，则要消耗一个槽位； * 如果遇到了非空节点，则除了消耗一个槽位外，还要再补充两个槽位 >此外，还需要将根节点作为特殊情况处理。 具体步骤如下： 1. 初始化槽位 `slot=1`，放置根节点的槽 2. 遍历，当字符串等于`','`时，上一个节点占用一个槽位， `slot--` 3. 如果`slot<0`， 直接返回false。没有槽位可以放置节点了。 4. 判断上一个节点是否为空节点，如果为空则占用一个槽位，如果不为空，则需要两个槽位。叶子节点需要两个槽 5. 遍历完毕，查看最后节点如果是空节点，，则槽的数量-1， slot--；如果最后节点不为空，则槽的数量+1， slot++。 6. 如果槽位等于0，则是有效二叉树。否则，则不是有效二叉树。 ```cpp bool test() { std::string a = "9,3,4,#,#,1,#,#,2,#,6,#,#"; int n = a.length(); int slot = 1; //放置根节点的槽 for (size_t i = 0; i < n; i++) { if (a.at(i) == ',') { slot --; //填充一个槽， 槽的数量-1 if (slot < 0) return false; //如果槽的数量<0则返回false if (a.at(i-1) != '#') slot+=2; //如果上一个节点不是空节点，则添加两个槽，叶子节点需要两个槽 } } if(a.at(n-1) == '#') slot--; //最后一个节点如果是空，槽的数量-1 else slot++; //最后一个节点如果不是是空， 槽的数量 + 1 return slot == 0; } ```