sdut原題鏈接
數(shù)據(jù)結構上機測試4.1:二叉樹的遍歷與應用1 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 輸入二叉樹的先序遍歷序列和中序遍歷序列，輸出該二叉樹的后序遍歷序列。
Input 第一行輸入二叉樹的先序遍歷序列； 第二行輸入二叉樹的中序遍歷序列。
Output 輸出該二叉樹的后序遍歷序列。
Example Input ABDCEF BDAECF
Example Output DBEFCA
Hint
Author
以下為accepted代碼
#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct node{ char date; struct node *left; struct node *right;}BinTree;BinTree *root;char st1[104], st2[104];BinTree * ans(int len, char *st1, char *st2)//二叉樹的建立與后序輸出{ BinTree *root; int i; if(len == 0)///判斷當前序列是否為空 return NULL; root = (BinTree *)malloc(sizeof(BinTree)); root->date = st1[0];//尋找根節(jié)點，根節(jié)點為先序序列st1的第一個 for(i = 0; i < len; i++)//尋找根節(jié)點在中序序列中的位置 { if(st2[i] == root->date) break; } root->left = ans(i, st1+1, st2);//（左子樹的長度，左子樹在st1中的開始位置，左子樹在st2中的開始位置） root->right = ans(len-i-1, st1+i+1, st2+i+1);//（右子樹的長度，右子樹在st1中的開始位置，右子樹在st2中的開始位置） printf("%c", root->date); return root;}int main(){ int len; scanf("%s %s", st1, st2); len = strlen(st1); ans(len, st1, st2);//調用二叉樹的建立與后序輸出函數(shù) printf("/n"); return 0;}/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 112KBSubmit time: 2017-02-07 17:25:34****************************************************/新聞熱點
疑難解答
