PTA数据结构与算法题目集(中文) 7-23

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

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

输入格式:

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

输出格式:

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

输入样例:

9
ABDFGHIEC
FDHGIBEAC

输出样例:

5
题目分析：利用前序遍历与中序遍历 计算树的高度 利用前序遍历找树节点 然后在中序遍历中限制范围
这个我写的最后一个测试点无法通过

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<stdio.h>
 3 
 4 int Find(char c, char str[], int Begin,int End)
 5 {
 6     for (int i = Begin; i < End; i++)
 7     {
 8         if (c == str[i])
 9             return i;
10     }
11     return -1;
12 }
13 
14 int GetHeight(char str1[], char str2[], int Length)
15 {
16     int Height = 0;
17     int Begin = 0;
18     int Flag = 0;
19     int End = Length;
20     int i = Find(str1[Flag], str2, Begin, End);
21     if (i == -1)
22         return Height;
23     Height++;
24     while (1)
25     {
26         if (End - Begin <= 0)
27             return Height;
28         if (i - Begin >=End - i-1)
29         {
30             End = i;
31             Flag++;
32         }
33         else
34         {
35             Flag += i - Begin + 1;
36             Begin = i + 1;
37         }
38         i = Find(str1[Flag], str2, Begin, End);
39         if (i == -1)
40             return Height;
41         Height++;
42     }
43 }
44 
45 int main()
46 {
47     char str1[52];
48     char str2[52];
49     int N;
50     scanf("%d", &N);
51     scanf("%s%s", str1,str2);
52     printf("%d", GetHeight(str1, str2, N));
53     return 0;
54 }

View Code

看了别人写的

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<stdio.h>
 3 
 4 int DFS(char str1[], char str2[], int n)
 5 {
 6     if (n == 0)
 7         return 0;
 8     int i = 0;
 9     for (i = 0; i < n && str1[0] != str2[i]; i++)
10         ;
11     int x = DFS(str1 + 1, str2, i)+1;  //左子树
12     int y = DFS(str1 + i + 1, str2 + i+1, n - i-1)+1; //右子树
13     return x > y ? x : y;
14 }
15 int main()
16 {
17     char str1[101];
18     char str2[101];
19     int N;
20     scanf("%d", &N);
21     scanf("%s%s", str1,str2);
22     printf("%d", DFS(str1, str2, N));
23     return 0;
24 }

View Code