还原二叉树

7-1 还原二叉树 (25 分)
给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

输入格式:

输入首先给出正整数n（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为n的不包含重复英文字母（区别大小写）的字符串。

输出格式:

输出为一个整数，即该二叉树的高度。

输入样例:

9
abdfghiec
fdhgibeac
输出样例:

5

include<stdio.h>

include<stdlib.h>

define max 50

typedef char elemtype;
typedef struct node *bintree;
struct node
{
elemtype data;
bintree left;
bintree right;
};
bintree recover(elemtype pre[],elemtype in[],int len)
{
bintree t;
int i;
if(!len)
return null;
else
{
t=malloc(sizeof(struct node));
t->data=pre[0];
for(i=0;i<len;i++) {
if(pre[0]==in[i])
break;
}
t->left=recover(pre+1,in,i);
t->right=recover(pre+1+i,in+i+1,len-i-1);
}
return t;
}
int gethigh(bintree t)
{
int hl,hr,maxh=0;
if(t){
hl=gethigh(t->left);
hr=gethigh(t->right);
maxh=hl>hr?hl:hr;
return (maxh+1);
}
else
return 0;
}
int main()
{
bintree tree;
elemtype preorder[max+1],inorder[max+1];
int n,h;
scanf("%d",&n);
scanf("%s",preorder);
scanf("%s",inorder);
tree=recover(preorder,inorder,n);
h=gethigh(tree);
printf("%d\n",h);
return 0;
}