[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)，代码如下：

	class Solution {
	public:
	bool isValidSerialization(string preorder) {
	int len = preorder.size(), i = 0;
	stack<string> st;
	bool isTree = false;
	while(i < len)
	{
	if(preorder[i] == '#')
	{
	if(st.empty() && i != len - 1)
	return false;
	if(st.size())
	st.pop();
	else
	isTree = true;
	}
	else if(isdigit(preorder[i]))
	{
	string num = "";
	while(isdigit(preorder[i]))
	num += preorder[i++];
	st.push(num);
	}
	++i;
	}
	return isTree;
	}
	};

view raw Verify Preorder Serialization of a Binary Tree.cpp hosted with ❤ by GitHub

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

	class Solution {
	public:
	bool isValidSerialization(string preorder) {
	int len = preorder.size(), hole = 1, i = 0;
	while(i < len)
	{
	if(preorder[i] != ',')
	--hole;
	if(hole < 0)return false;
	if(isdigit(preorder[i]))
	{
	while(isdigit(preorder[i]))
	++i;
	hole += 2;
	}
	++i;
	}
	return !hole;
	}
	};

view raw Verify Preorder Serialization of a Binary Tree_2.cpp hosted with ❤ by GitHub