數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)之二叉樹四：還原二叉樹 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic PRoblem Description
給定一棵二叉樹的先序遍歷序列和中序遍歷序列，要求計(jì)算該二叉樹的高度。 Input
輸入數(shù)據(jù)有多組，每組數(shù)據(jù)第一行輸入1個(gè)正整數(shù)N(1 <= N <= 50)為樹中結(jié)點(diǎn)總數(shù)，隨后2行先后給出先序和中序遍歷序列，均是長(zhǎng)度為N的不包含重復(fù)英文字母(區(qū)分大小寫)的字符串。 Output
輸出一個(gè)整數(shù)，即該二叉樹的高度。 Example Input
9 ABDFGHIEC FDHGIBEAC Example Output
5 Hint
大言不慚的說(shuō)說(shuō)水題。。雖然做的過(guò)程并不一帆風(fēng)順
#include <stdio.h>#include <stdlib.h>typedef struct node{ char data; struct node *l,*r;}node;node *create(int len,char *pre,char *in)//老套路了，知道先序和中序搞出整棵樹{ int i; node *root; if(len<=0) return NULL; else{ root = (node *)malloc(sizeof(struct node)); char x = pre[0]; root->data = x; for(i=0; i<len; i++){ if(in[i]==x) break; } root->l = create(i,pre+1,in); root->r = create(len-i-1,pre+i+1,in+i+1); } return root;}int deep(node *root)//求深度的話，就看左右子樹哪個(gè)更深就返回哪個(gè)的深度，最后加個(gè)1就是整棵樹的深度了{(lán) int d = 1; if(root){ int dl = deep(root->l); int dr = deep(root->r); d = dl>dr?dl+1:dr+1; } else return 0;//一定到最后沒有左右子樹的話要返回0，這樣就不會(huì)又加1了 return d;}int main(){ int len; char pre[100],in[100]; while(~scanf("%d",&len)){ scanf("%s %s",pre,in); node *root = create(len,pre,in); printf("%d/n",deep(root)); } return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
