【题目】
输入一个整数数组,判断该数组是不是某二叉查找树的后序遍历的结果。如果是返回true,否则返回false。
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
8
/ \
610
/ \ / \
5 7 9 11
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。
【分析】
这是一道trilogy的笔试题,主要考查对二叉查找树的理解。
在后续遍历得到的序列中,最后一个元素为树的根结点。从头开始扫描这个序列,比根结点小的元素都应该位于序列的左半部分;
从第一个大于跟结点开始到跟结点前面的一个元素为止,所有元素都应该大于跟结点,因为这部分元素对应的是树的右子树。
根据这样的划分,把序列划分为左右两部分,我们递归地确认序列的左、右两部分是不是都是二叉查找树。
【代码】
/*********************************
* 日期:2013-12-20
* 作者:SJF0115
* 题目: 6.二叉查找树的后序遍历结果
* 来源:trilogy
* 分类:程序员面试题精选100题
**********************************/
#include <iostream>
using namespace std;
// 判断是否是二叉查找树的后序遍历结果
// array 整数数组
// n 数组元素个数
bool IsPostOrder(int array[],int n){
if(array == NULL || n <= 0){
return false;
}
int index = 0;
// 前半部分(左子树)小于最后一个元素(根节点)
for(int i = 0;i < n-1;i++){
if(array[i] > array[n-1]){
index = i;
break;
}//if
}//for
// 后半部分(右子树)大于最后一个元素(根节点)
for(int i = index;i < n-1;i++){
if(array[i] < array[n-1]){
return false;
}//if
}//for
// 判断左子树是否满足
bool left = true;
if(index > 0){
left = IsPostOrder(array,index);
}
// 判断右子树是否满足
bool right = true;
if(index < n-1){
right = IsPostOrder(array+index,n-index-1);
}
return left&&right;
}
int main(){
int a[] = {5,7,6,9,11,10,8};
cout<<IsPostOrder(a,7)<<endl;
int b[] = {7,4,6,5};
cout<<IsPostOrder(b,4)<<endl;
int c[] = {7};
cout<<IsPostOrder(c,1)<<endl;
return 0;
}
分享到:
相关推荐
程序员面试题精选100题
程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试...
程序员面试题精选100题完整版.pdf,这是一份不错的文件
程序员面试题精选100题
程序员面试题精选程序员面试题精选程序员面试题程序员面试题精选精选
程序员面试试题.txt程序员面试试题.txt程序员面试试题.txt程序员面试试题.txt
程序员面试题精选100题
------------------------------------- java程序员早期面试题汇总 BAT经典面试题汇总.pdf Java常考面试题.pdf java面试题(题库全)....程序员面试题精选100题.pdf ... -------------------------------------
程序员面试题精选100题(2008)程序员面试题精选100题(2008)
程序员面试题精选100例.doc