sdut原題鏈接
數據結構實驗之二叉樹四：還原二叉樹 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 給定一棵二叉樹的先序遍歷序列和中序遍歷序列，要求計算該二叉樹的高度。
Input 輸入數據有多組，每組數據第一行輸入1個正整數N(1 <= N <= 50)為樹中結點總數，隨后2行先后給出先序和中序遍歷序列，均是長度為N的不包含重復英文字母(區(qū)分大小寫)的字符串。
Output 輸出一個整數，即該二叉樹的高度。
Example Input 9 ABDFGHIEC FDHGIBEAC
Example Output 5
Hint
Author xam
以下為accepted代碼
#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct node{ char date; struct node *left; struct node *right;}BinTree;BinTree *root;int len;char st1[54], st2[54];BinTree * ans(int len, char *st1, char *st2)//建立二叉樹函數{ if(len == 0) return NULL; int i; BinTree *root; root = (BinTree *)malloc(sizeof(BinTree)); root->date = st1[0];//尋找根節(jié)點，新的根節(jié)點為st1的第一個 for(i = 0; i < len; i++)//尋找新的根節(jié)點在中序序列st2中的位置 { 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中的開始位置） return root;}int get_hight(BinTree *root)//計算二叉樹的深度函數{ int HL, HR, MAXH; if(root) { HL = get_hight(root->left); HR = get_hight(root->right); MAXH = HL>HR? HL: HR; return (MAXH + 1); } else return 0;}int main(){ int n, y; while(scanf("%d", &n) != EOF) { scanf("%s %s", st1, st2); root = ans(n, st1, st2);//調用建立二叉樹函數 y = get_hight(root);//調用計算二叉樹的深度函數 printf("%d/n", y); } return 0;}/***************************************************User name: jk160630Result: AcceptedTake time: 0msTake Memory: 116KBSubmit time: 2017-02-07 19:21:23****************************************************/新聞熱點
疑難解答
