河北大学程序设计训练营

题目要求：

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

输入格式:

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

输出格式:

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

输入样例:

9
ABDFGHIEC
FDHGIBEAC

输出样例:

5

先看怎么恢复二叉树：
先序遍历第一个字母即为树的根，其他字母可视为子树的根。
中序遍历中字母的位置为相对位置，比如，BAC ，就是
在这里插入图片描述

恢复就是在先序遍历中找子树的根，然后在中序遍历里判断它的左右子树，以题目为例，
这样就恢复完了。
在这里插入图片描述

再来看怎么求二叉树高度：
迭代分别求左右子树的高度，较高的就为树的高度。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>

using namespace std;

string str1,str2;

int Height(int t1,int t2,int lenth,int H)
{
    //高度为零
    if(lenth == 0)
        return H-1;

    int len = 0;
    while(1)
    {
        if(str2[t2+len] == str1[t1])
            break;
        len++;       
    }

    int h1 = Height(t1+1,t2,len,H+1);        //左子树最大高度
    int h2 = Height(t1+len+1,t2+len+1,lenth-1-len,H+1);  //右子树最大高度

    return h1 > h2 ? h1:h2;
}

int main(){
    int N;
    cin>>N>>str1>>str2;
    printf("%d",Height(0,0,N,1));
    return 0;
}