判斷整數(shù)序列是否為二元查找樹的后序遍歷結(jié)果的解決方法
更新時(shí)間：2013年05月28日 17:06:18 作者：
本篇文章是對(duì)判斷整數(shù)序列是否為二元查找樹的后序遍歷結(jié)果的解決方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
題目：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。
如果是返回true，否則返回false。
例如輸入5、7、6、9、11、10、8，由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果.
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果輸入7、4、6、5，沒有哪棵樹的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。
本題網(wǎng)上已經(jīng)有用遞歸單純判斷的解法.
個(gè)人解法: 先得到序列對(duì)應(yīng)的中序序列, 然后看中序序列是否從小到大有序, 得出判斷.
相比:時(shí)間復(fù)雜度相同, 增加N的空間, 但可求得對(duì)應(yīng)的中序序列.
以下為代碼:
#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() */
如果是返回true，否則返回false。
例如輸入5、7、6、9、11、10、8，由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果.
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果輸入7、4、6、5，沒有哪棵樹的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。
本題網(wǎng)上已經(jīng)有用遞歸單純判斷的解法.
個(gè)人解法: 先得到序列對(duì)應(yīng)的中序序列, 然后看中序序列是否從小到大有序, 得出判斷.
相比:時(shí)間復(fù)雜度相同, 增加N的空間, 但可求得對(duì)應(yīng)的中序序列.
以下為代碼:
復(fù)制代碼 代碼如下:
#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() */
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)哈夫曼編碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-04-04
本文實(shí)現(xiàn)對(duì)C++使用UDP做了簡(jiǎn)單封裝,實(shí)現(xiàn)通訊,包括服務(wù)端和客戶端,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-12-12
C++11 引入了智能指針的概念，使用了引用計(jì)數(shù)的想法，讓程序員不再需要關(guān)心手動(dòng)釋放內(nèi)存。關(guān)于C++指針得內(nèi)容下面文章將為大家做一個(gè)詳細(xì)介紹2021-09-09
C++實(shí)現(xiàn)LeetCode(120.三角形)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(120.三角形),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
OpenCV使用稀疏光流實(shí)現(xiàn)視頻對(duì)象跟蹤的方法詳解
這篇文章主要為大家詳細(xì)介紹了OpenCV如何使用稀疏光流實(shí)現(xiàn)視頻對(duì)象跟蹤功能，文中的示例代碼講解詳細(xì)，具有一定的借鑒價(jià)值，需要的可以參考一下2023-02-02
C語言中enum關(guān)鍵字的實(shí)現(xiàn)示例
這篇文章主要介紹了C語言中enum關(guān)鍵字的實(shí)現(xiàn)示例，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
C語言實(shí)現(xiàn)的循環(huán)單鏈表功能示例
這篇文章主要介紹了C語言實(shí)現(xiàn)的循環(huán)單鏈表功能,結(jié)合實(shí)例形式分析了基于C語言實(shí)現(xiàn)的循環(huán)單鏈表定義、創(chuàng)建、添加、刪除、打印、排序等相關(guān)操作技巧,需要的朋友可以參考下2018-04-04
c語言 字符串轉(zhuǎn)大寫的簡(jiǎn)單實(shí)例
這篇文章主要介紹了c語言 字符串轉(zhuǎn)大寫的簡(jiǎn)單實(shí)例，有需要的朋友可以參考一下2013-12-12
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)二叉樹基本操作，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能給你帶來幫助2021-08-08
這篇文章主要為大家詳細(xì)介紹了如何利用C++制作一個(gè)當(dāng)下很火的人生模擬器游戲，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-05-05