sdut原題鏈接
迷失の搜索樹 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 小璐在機(jī)緣巧合之下獲得了一個二叉搜索樹，這個二叉搜索樹恰好有n個節(jié)點，每個節(jié)點有一個權(quán)值，每個節(jié)點的權(quán)值都在[1,n]這個區(qū)間內(nèi)，并且兩兩不相同，真是優(yōu)美的性質(zhì)啊 但是命運的不公又讓她失去了這個二叉搜索樹 幸運的是，她還記得自己丟失的二叉搜索樹的前序遍歷序列。 在丟了二叉搜索樹之后，小璐無比想念她的這個樹的后序遍歷 那么問題來了，聰明的你在知道這個二叉搜索樹的前序遍歷的序列的情況下，能幫她找到這個二叉搜索樹的后序遍歷嘛?
Input 多組輸入，以文件結(jié)尾 每組數(shù)據(jù)第一行為一個整數(shù)n，代表這個二叉搜索樹的節(jié)點個數(shù)(1<=n<=100) 接下來一行n個整數(shù)，代表這個二叉搜索樹的前序遍歷序列
Output 輸出n個整數(shù) 表示這個二叉樹的后序遍歷序列
Example Input 5 4 2 1 3 5
Example Output 1 3 2 5 4
Hint 二叉查找樹是一棵空樹，或者是具有下列性質(zhì)的二叉樹： 若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值 若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值 它的左、右子樹也分別為二叉排序樹 Author 2016暑假集訓(xùn)結(jié)訓(xùn)賽 by QAQ
以下為accepted代碼
#include <stdio.h>#include <stdlib.h>typedef struct node{ int date; struct node *left; struct node *right;}BinTree;BinTree *root;int num[140], flag;BinTree * Insert(BinTree *rt, int x)//二分查找樹的插入算法{ if(!rt){ rt = (BinTree *)malloc(sizeof(BinTree)); rt->date = x; rt->left = rt->right = 0; } else { if(x < rt->date) rt->left = Insert(rt->left, x); else rt->right = Insert(rt->right, x); } return rt;}void last_put(BinTree *rt)//中序遍歷{ if(rt) { last_put(rt->left); last_put(rt->right); num[flag++] = rt->date; }}int main(){ int n, i, x; while(scanf("%d", &n) != EOF) { flag = 0;///注意初始化 root = NULL;///注意初始化 for(i = 0; i < n; i++) { scanf("%d", &x); root = Insert(root, x);//調(diào)用二分查找樹的插入函數(shù) } last_put(root);//調(diào)用中序遍歷函數(shù) for(i = 0; i < n; i++) { printf("%d%c", num[i], i == n-1? '/n': ' '); } } return 0;}/***************************************************User name: jk160630Result: AcceptedTake time: 8msTake Memory: 584KBSubmit time: 2017-02-08 18:26:18****************************************************/以下為runtime error代碼
#include <stdio.h>#include <stdlib.h>typedef struct node{ char date; struct node *left; struct node *right;} BinTree;BinTree *rt;int num[140];int flag;BinTree * get_build(int len, char *st1, char *st2){ if(len == 0) return NULL; int i; BinTree *root; root = (BinTree *)malloc(sizeof(BinTree)); root->date = st1[0]; for(i = 0; i < len; i++) { if(st2[i] == root->date) break; } root->left = get_build(i, st1+1, st2); root->right = get_build(len-i-1, st1+i+1, st2+i+1); num[flag++] = root->date - '0'; return root;}int cmp(const void *a, const void *b){ return ((*(char *)a)-(*(char *)b));}int main(){ int n, i, x; char st1[140], st2[140]; while(scanf("%d", &n) != EOF) { for(i = 0; i < n; i++) { scanf("%d", &x); st1[i] = x + '0'; st2[i] = st1[i]; } qsort(&st2[0], n, sizeof(st2[0]), cmp); ///printf("%s/n", st2); rt = get_build(n, st1, st2); for(i = 0; i < n; i++) { printf("%d%c", num[i], i == n-1? '/n': ' '); } } return 0;}/***************************************************User name: jk160630Result: Runtime ErrorTake time: 0msTake Memory: 0KBSubmit time: 2017-02-08 17:54:56****************************************************/新聞熱點
疑難解答
