首页 > 代码库 > 【剑指offer】二叉搜索树的后序遍历序列

【剑指offer】二叉搜索树的后序遍历序列

转载请注明出处:http://blog.csdn.net/ns_code/article/details/26092725


    剑指offer上的第24题,主要考察递归思想,九度OJ上AC。

题目描述:

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

输入:

每个测试案例包括2行:

第一行为1个整数n(1<=n<=10000),表示数组的长度。

第二行包含n个整数,表示这个数组,数组中的数的范围是[0,100000000]。

输出:

对应每个测试案例,如果输入数组是某二叉搜索树的后序遍历的结果输出Yes,否则输出No。

样例输入:
7
5 7 6 9 11 10 8
4
7 4 6 5
样例输出:
Yes
No
    要紧紧抓住二叉搜索树的特点,对于后序遍历序列,其每个子树的最后一个元素会比前面的左边一部分大,右边一部分小,这样便可以通过递归来判断。

    AC代码如下:

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

bool IsBehSequenceBST(int *seq,int len)
{
	if(seq==NULL || len<1)
		return false;

	int root = seq[len-1];
	int i;
	for(i=0;i<len-1;i++)
		if(seq[i]>root)
			break;

	//第一个右子树元素的下标
	int RightStart = i;

	for(;i<len-1;i++)
		if(seq[i]<root)
			return false;
 
	bool left = true;
	if(RightStart > 0)
		left = IsBehSequenceBST(seq,RightStart);
	bool right = true;
	if(RightStart < len-1-RightStart)
		right = IsBehSequenceBST(seq+i,len-RightStart-1);

	return (left && right);

}

int main()
{
	int n;
	while(scanf("%d",&n) != EOF)
	{
		int *seq = (int *)malloc(n*sizeof(int));
		if(seq == NULL)
			exit(EXIT_FAILURE);

		int i;
		for(i=0;i<n;i++)
			scanf("%d",seq+i);
		if(IsBehSequenceBST(seq,n))
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}

/**************************************************************
    Problem: 1367
    User: mmc_maodun
    Language: C
    Result: Accepted
    Time:70 ms
    Memory:1308 kb
****************************************************************/