給定一棵二叉樹的先序遍歷序列和中序遍歷序列，要求計算該二叉樹的高度。 Input
輸入數據有多組，每組數據第一行輸入1個正整數N(1 <= N <= 50)為樹中結點總數，隨后2行先后給出先序和中序遍歷序列，均是長度為N的不包含重復英文字母(區分大小寫)的字符串。 Output
輸出一個整數，即該二叉樹的高度。 Example Input
9 ABDFGHIEC FDHGIBEAC Example Output
5 Hint
Author
xam
#include<stdio.h>#include<string.h>#include<stdlib.h>char a[55];char b[55];struct node{ int data; struct node *l, *r;};struct node *creat(int n, char *a, char *b){ int i; if(n == 0) return NULL; struct node *root; root = (struct node *) malloc (sizeof(struct node)); root -> data = a[0]; for(i = 0; i < n; i++) { if(b[i] == a[0]) break; } root -> l = creat(i, a+1, b); root -> r = creat(n-1-i, a+1+i, b+1+i); return root;};int high(struct node *root){ int d1, d2; if(root) { d1 = high(root -> l); d2 = high(root -> r); return d1 > d2? d1+1 : d2+1; } else return 0;}int main(){ int t, n; while(~scanf("%d", &t)) { scanf("%s%s", a, b); struct node *root; n = strlen(a); root = creat(n, a, b); printf("%d/n", high(root)); } return 0;}新聞熱點
疑難解答
