手机
当前位置:查字典教程网 >编程开发 >C语言 >判断整数序列是否为二元查找树的后序遍历结果的解决方法
判断整数序列是否为二元查找树的后序遍历结果的解决方法
摘要:题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。例如输入5、7、6、9、11、...

题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。

如果是返回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("yesn");

}

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++函数中return语句的使用方法

深入理解二叉树的非递归遍历

判断一个数是不是素数的方法

深入遍历二叉树的各种操作详解(非递归遍历)

精品推荐
分类导航