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

题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回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() */
您可能感兴趣的文章:C#使用前序遍历、中序遍历和后序遍历打印二叉树的方法二叉树的非递归后序遍历算法实例详解探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)C语言数据结构树之后序遍历的实现

方法 后序遍历 遍历