二叉搜索树的后序遍历序列

题目大意：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

九度OJ链接：http://ac.jobdu.com/problem.php?pid=1367

分析：本题给定一个序列，要求判断该序列是否是二叉搜索树（二叉查找树）的后序遍历结果。二叉搜索树的特点即是中序遍历得到升序，非叶子节点的左子树中的节点值一定比根节点小，右子树中的节点值一定比根节点大，每个子树都满足这种条件。根据其后序遍历得到序列的特点即可得出判读方法。

C++实现：

#include <iostream>
#include <stdio.h>
#include <vector>
#include <memory.h>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>
#include <fstream>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;

bool isBinarySearchTree(vector<int> &a, int start, int end)
{
	if(start >= end)
		return true;
	int i = start;
	while(i < end)
	{
		if(a[i] > a[end])
			break;
		i ++;
	}
	int j = i; 
	while(j < end)
	{
		if(a[j] < a[end])
			return false;
		j ++;
	}
	return isBinarySearchTree(a, start, i-1) &&
		isBinarySearchTree(a, i, end-1);
}

void input()
{
//	freopen("c:/input.txt","r",stdin);
	int n;
	while(scanf("%d", &n) != EOF)
	{
		vector<int> a;
		int x;
		while(n-- > 0)
		{
			scanf("%d", &x);
			a.push_back(x);
		}
		bool res = isBinarySearchTree(a, 0, a.size() - 1);
		if(res)
			printf("Yes");
		else
			printf("No");
		printf("
");
	}
}

int main()
{
	input();
	return 0;
}