服务器之家

服务器之家 > 正文

判断整数序列是否为二元查找树的后序遍历结果的解决方法

时间:2020-12-11 15:39     来源/作者:C语言教程网

题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true,否则返回false。
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果.
      8
     / \
   6   10
  / \    / \
  5  7 9 11
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。
本题网上已经有用递归单纯判断的解法.
个人解法: 先得到序列对应的中序序列, 然后看中序序列是否从小到大有序, 得出判断.
相比:时间复杂度相同, 增加N的空间, 但可求得对应的中序序列.
以下为代码:

复制代码 代码如下:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LEN 100
int seq[LEN + 1] = {0};
int *mid = NULL;
int pos = 1;
void getmid(int start, int end);
int check(int num);
int main()
{
 int val;
 int num;
 int ret;
 int i;
 printf("input the sequence, end it with '-9999': ");

 num = 1;
 scanf("%d", &val);
 while(val != -9999)
 {
  seq[num] = val;
  num ++;
  scanf("%d", &val);
 }
 num--;
 mid = (int *)malloc((num + 1) * sizeof(int));
 if(mid == NULL)
 {
  printf("malloc failed.\n");
  exit(1);
 }
 memset(mid, 0, num + 1);
 getmid(1, num);

 printf("mid: ");
 for(i = 1; i< num +1; i++)
 {
  printf("%d ", mid[i]);
 }
 printf("\n");
 ret = check(num);
 if(ret == -1)
 {
  printf("no.\n");
 }
 else
 {
  printf("yes\n");
 }
 return 0;
}/* main() */
void getmid(int start, int end)
{
 int flag;
 if(start > end)
 {
  return;
 }
 if(start == end)
 {
  mid[pos] = seq[end];
  pos ++;
  return;
 }
 int par;
 par = start;
 flag = 0;
 while(par < end)
 {
  if(seq[par] > seq[end])
  {
   flag = 1;
   getmid(start, par - 1);
   mid[pos] = seq[end];
   pos ++;   
   getmid(par, end - 1);
   break;
  }
  par ++;
 }
 if(!flag)
 {
  getmid(start, end-1);
  mid[pos] = seq[end];
  pos ++;
 }
}/* getmid */
int check(int num)
{
 int i;

 for(i = 1; i < num; i++)
 {
  if(mid[i] > mid[i+1])
  {
   return -1;
  }
 }
 return 0;
}/* check() */

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址 2020-08-12
最新idea2020注册码永久激活(激活到2100年)
最新idea2020注册码永久激活(激活到2100年) 2020-07-29
返回顶部