[LeetCode]Verify Preorder Serialization of a Binary Tree

我们首先明确一点，什么时候这个序列是不合理的。那么只可能有两种情况：

• tree已经建成，但是后面还有跟着的字符串
• tree还没有建成，字符串已经完结

具体来讲，当树还没有建成的时候，还有很多的空的节点需要我们用number或者#去填。每填一个number，我们可以填一个空位，但是会新增两个空位；每填一个#，我们可以消除一个空位，并不会引入新的空位。我们只需要检测空位有没有全部填满，因为这样才是一个valid的tree，并且input string有没有全部用完。

很显然我们用Preroder Traversal可以做，tree有没有建成或者追踪填满的时候有没有到input string的末尾。时间复杂度O(n)，空间复杂度O(log n)，代码如下：

另外还有另一种方法，就是计算空位的数量。像我们之前分析的一样，填入不同的元素我们可以消去空位和引入空位，那么我们只需要一直追踪空位的数量即可，空位数量最终一定为0，并且每时每刻不能为负数，开始的时候默认空位数为1。时间复杂度O(n)，空间复杂度O(1)，代码如下: