如何区分整数数组是不是二元查找树的后序遍历结果
来源：爱站网时间：2021-06-21编辑：网友分享
后序遍历（LRD）是二叉树遍历的一种，那么当输入有一个整数数组时，要如何区分这个数组是不是二元查找树的后序遍历结果？下面爱站技术频道小编将为大家分享详细的解决方法，如果不清楚的朋友可以跟着小编一起往下看。
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果.
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。
本题网上已经有用递归单纯判断的解法.
个人解法: 先得到序列对应的中序序列, 然后看中序序列是否从小到大有序, 得出判断.
相比:时间复杂度相同, 增加N的空间, 但可求得对应的中序序列.
以下为代码:
#include
#include
#include
#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 {
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 {
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 {
if(mid[i] > mid[i+1])
{
return -1;
}
}
return 0;
}/* check() */
以上就是爱站技术频道小编为大家分享的关于判断整数序列是否为二元查找树的后序遍历结果的解决方法，同时还为大家分享了详细的代码内容。
下一篇：深入解析关于阶乘的相关知识
