首页 > 代码库 > 【剑指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
****************************************************************/
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。