大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。
转载请注明出处: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
****************************************************************/
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118828.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...