[LeetCode]Verify Preorder Sequence in Binary Search Tree

给定Preorder序列，如果是valid的话，构造出来的BST应该是唯一的。那么什么样的input是不valid的呢？首先我们肯定递增序列是不会有问题的，因为我们可以一直构建右子节点来满足条件，比如1,2,3,4,5的序列，就是从1开始一直去右子节点到5。换句话说，对于input number来说，没有右边界，输入多大的数都是合理的。那么问题就出在递减序列，也就是说对于某些数来说，是有左边界的。具体来讲，如果出现递减序列，说明进入了当前节点c的左子节点left，如果当前节点是某个节点n的右子树，那么left的值必须大于n的值，也就是说，碰到这种情况的时候我们才能断定，当前preorder序列是不合理的。
具体到算法，我们如何实现呢? 我们做Preorder Traversal即可，注意更新当前的左边界。时间复杂度O(n)，空间复杂度O(log n)，代码如下：

	class Solution {
	public:
	bool verifyPreorder(vector<int>& preorder) {
	int len = preorder.size(), i = 0, leftBound = INT_MIN;
	stack<int> st;
	while(i < len)
	{
	int num = preorder[i];
	if(st.size() && num < leftBound)
	return false;
	if(st.empty() || st.top() > num)
	st.push(num);
	else
	{
	while(st.size() && st.top() < num)
	{
	leftBound = st.top();
	st.pop();
	}
	st.push(num);
	}
	++i;
	}
	return true;
	}
	};

view raw Verify Preorder Sequence in Binary Search Tree_1.cpp hosted with ❤ by GitHub

这道题还可以用Divide and Conquer来做，因为我们知道当前区间是一个tree，并且第一个数是root，那么我们可以在O(n)的时间里做二分，找到哪一半是左子树，哪一半是右子树。找到之后，我们继续递归地判断子树是不是valid的即可。
时间复杂度分析T = 2 * T / 2 + n，那么对于每一层递归来说耗时分别为n, n / 2 * 2, n / 4 * 4，总共有log n层，我们可以得到T = n * log n，所以时间复杂度为O(n * log n)，空间复杂度为O(log n)。代码如下：

	class Solution {
	public:
	bool verifyPreorder(vector<int>& preorder) {
	int len = preorder.size();
	return verify(preorder, 0, len - 1, INT_MIN);
	}
	private:
	bool verify(vector<int>& preorder, int lo, int hi, int leftBound)
	{
	if(hi <= lo)return true;
	int root = preorder[lo], split = hi + 1;
	for(int i = lo + 1; i <= hi; ++i)
	{
	int num = preorder[i];
	if(num < leftBound)
	return false;
	if(num > root)
	{
	split = i;
	break;
	}
	}
	return verify(preorder, lo + 1, split - 1, leftBound) && verify(preorder, split, hi, root);
	}
	};

view raw Verify Preorder Sequence in Binary Search Tree_2.cpp hosted with ❤ by GitHub