首页 > ACM题库 > 九度OJ > 剑指offer(12)-二叉搜索树的后序遍历序列[数据结构]九度1367
2013
12-28

剑指offer(12)-二叉搜索树的后序遍历序列[数据结构]九度1367

题目来自剑指offer系列 九度 1367:http://ac.jobdu.com/problem.php?pid=1367

题目描述:
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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

对应二叉树的问题普遍是用递归解决。二叉搜索树也就是二分查找树。左子树的每个节点都比根节点小,右子树的每个节点都比根节点大。

以 5 7 6 9 11 10 8 为例: 根节点为8,左子树为 5 7 6  又子树为 11 10。

所以,任务就是先找到左子树。

程序中是这样找的:

int k = start; //k为右子树的开始位置(左子树都是比根节点小的数)
while(arr[k] < arr[end] && k <= end-1) k++;

此时,arr[k] == 11。即右子树开始的位置。 接下来判断右子树是否是符合要求的,即都比根节点大。

//============================================================================
// Name        : 二叉搜索树的后序遍历序列.cpp
// Author      : coder
// Version     :
// Copyright   : www.acmerblog.com
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <stdio.h>
int n, arr[10001], j;
bool check(int start, int end){
	//任意3个或3个以下的数都符合
	if(start >= end-2) return true;
	int k = start; //k为右子树的开始位置(左子树都是比根节点小的数)
	while(arr[k] < arr[end] && k <= end-1) k++;
	j = k;
	//只要右子树中有比根节点小的就不符合
	while(j < end) if(arr[j++] < arr[end]) return false;
	return check(start,k-1) && check(k,end-1); //分别判断左右子树
}
int main() {
	while(scanf("%d", &n) != EOF){
		for(int i=0; i<n; i++) scanf("%d", &arr[i]);
		if( check(0,n-1) ) puts("Yes");
		else puts("No");
	}
	return 0;
}

 


  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?