BST的后序遍历序列

递归：

bool pp(const vector<int> vi, int start, int end)
{
	if (start >= end)return 1;
	int i = start;
	while (i <= end && vi[i] < vi[end])i++;
	for (int j = i;j <= end;j++)if (vi[j] < vi[end])return 0;
	return pp(vi, start, i - 1) && pp(vi, i, end - 1);
}
bool VerifySquenceOfBST(vector<int> sequence)
{
	if (sequence.empty())return 0;
	if (sequence.size() == 1)return 1;
	return pp(sequence, 0, sequence.size() - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

思路：后序遍历的最后一个元素一定是树根。除树根外，前面的元素可以分为两部分，左子树的值和右子树的值。左子树的值都小于根，右子树的值都大于根。如果在递归过程中发现右子树的值小于根，那么false。

非递归：

bool VerifySquenceOfBST(vector<int> sequence)
{
	if (sequence.empty())return 0;
	if (sequence.size() == 1)return 1;
	int i = 0, size = sequence.size() - 1;
	while (size > 0)
	{
		while (sequence[i] < sequence[size])i++;
		while (sequence[i] > sequence[size])i++;
		if (i < size)return 0;
		i = 0;
		size--;
	}
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15