剑指OFFER之从二叉搜索树的后序遍历序列（九度OJ1367）
剑指OFFER之从二叉搜索树的后序遍历序列（九度OJ1367）
用户1154259
发布于 2018-01-17 09:52:36
发布于 2018-01-17 09:52:36
题目描述：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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解题思路：
首先我们观察题目：二叉搜索树，后序遍历两个知识点。
二叉搜索树，用于搜索，因此内部节点没有重复的元素。另外，满足二叉树的性质，左子树都比自己小，右子树都比自己大。那么可想而知，如果按照后序遍历，先左后右最后自己的顺序来遍历树，数组的最后一个元素肯定是自己（父节点），然后剩余的部分分成两个部分，第一部分都比自己小（左子树部分），第二部分都比自己大（右子树部分），因此套用这个关系就可以循环检验出是否是二叉搜索树的后序遍历了。
int isPost(int i,int j){
if(i == j)
return 1;
else{
int k=j-1;
while(k>=i){
if(test[k] > test[j])
k--;
else
break;
}
int flag = k;
while(k>=i){
if(test[k] < test[j])
k--;
else
break;
}
if(k == i-1){
if(test[i]>test[j] || test[j-1]<test[j] ){
//printf("(%d-%d)\n",i,j-1);
return isPost(i,j-1);
}else{
//printf("(%d-%d)(%d-%d)\n",i,flag,flag+1,j-1);
return (isPost(i,flag))&&(isPost(flag+1,j-1));
}
}else{
return 0;
}
}
}另外要注意的是，本题的二叉树并非满二叉树，因此可能出现下面的测试代码：
3
1 2 3也就是说，这个树的父节点，只有左子树，没有右子树（右孩子），但是这个测试用例仍然是要通过的。因此需要外加一个判断，判断是否仅有单个孩子子树
if(test[i]>test[j] || test[j-1]<test[j] ){
//printf("(%d-%d)\n",i,j-1);
return isPost(i,j-1);
}全部代码：
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
int test[10005]={0};
int isPost(int i,int j);
int main(){
int n,i;
while(scanf("%d",&n)!=EOF){
for(i=0;i<n;i++)
scanf("%d",&test[i]);
if(isPost(0,n-1))
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
int isPost(int i,int j){
if(i == j)
return 1;
else{
int k=j-1;
while(k>=i){
if(test[k] > test[j])
k--;
else
break;
}
int flag = k;
while(k>=i){
if(test[k] < test[j])
k--;
else
break;
}
if(k == i-1){
if(test[i]>test[j] || test[j-1]<test[j] ){
//printf("(%d-%d)\n",i,j-1);
return isPost(i,j-1);
}else{
//printf("(%d-%d)(%d-%d)\n",i,flag,flag+1,j-1);
return (isPost(i,flag))&&(isPost(flag+1,j-1));
}
}else{
return 0;
}
}
}
/**************************************************************
Problem: 1367
User: xhalo
Language: C
Result: Accepted
Time:10 ms
Memory:952 kb
****************************************************************/本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014-06-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录