5-23 还原二叉树 (25分)

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

输入格式:

输入首先给出正整数N（

输出格式:

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

输入样例:

9
ABDFGHIEC
FDHGIBEAC

输出样例:

5

动态规划的东西好难啊，测试点没有全部通过，还要再试试。。。。。。

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 using namespace std;
 5 typedef struct Node *Bintree;
 6 typedef struct Node{
 7     char data;
 8     Bintree left;//左子树
 9     Bintree right;//右子树
10 }Node;
11 Bintree Recover(char pre[],char mid[],int len)
12 {
13     Bintree T;int i;
14     if(!len) return NULL;
15     else{
16         T=(Bintree)malloc(sizeof(struct Node));
17         T->data=pre[0];
18         for(i=0;i<len;i++)
19         {
20             if(pre[0]==mid[i])
21                 break;
22         }
23         T->left=Recover(pre+1,mid,i);
24         T->right=Recover(pre+1+i,mid+1+i,len-1-i);
25     }
26     return T;
27 }
28 
29 int GetHigh(Bintree T)
30 {
31     int HL,HR,Height;
32     if(!T)
33         return 0;
34     else
35     {
36         HL=GetHigh(T->left);
37         HR=GetHigh(T->right);
38         Height=HL>HR?HL:HR;
39         Height++;//树高为左右树高较大者加1
40     }
41     return Height;
42 }
43 
44 int main()
45 {
46     Bintree T;
47     int num,h;
48     char preorder[11],inorder[11];
49     cin>>num;
50     cin>>preorder>>inorder;//输入先序遍历和中序遍历
51     T=Recover(preorder,inorder,num);
52     h=GetHigh(T);
53     cout<<h<<endl;
54     return 0;
55 }