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

输入格式:

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

输出格式:

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

输入样例:

1
2
3
9
ABDFGHIEC
FDHGIBEAC

输出样例:

1
5

思路：

​ 这题有点难理解

还原二叉树：

已知一颗二叉树:

先序遍历：ABCDEF
中序遍历：CBAEDF
由于前序遍历第一个打印的是 A 所以 A 为根结点
由于中序遍历 CBAEDF 可知 C 和 B 是 A 的左子树的结点，E、D、F 是 A 右子树的结点

由于前序遍历中先 B 后 C ，所以 B 是 A 的左孩子，C 只能是 B 的孩子。
中序遍历中先 C 后 B ，所以 C 是 B 的左孩子

前序遍历中顺序为 DEF，意味着 D 是 A 的右孩子
E、F 是 D 的子孙，但不一定是左右孩子，可能有一个孙子
中序遍历中顺序为 EDF，所以 E 是 D 的左孩子，F 是 D 的右孩子

求树的高度：

树的高度其实是用递归来求得，树的高度=max(左子树的高度,右子树的高度) + 1(当前自己这一层),对于左子树和右子树也是这个公式，递归求解即可。

代码：

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
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
typedef struct TreeNode{
    char data;
    TreeNode* left;
    TreeNode* right;
}*Tree;
int n;
string pre,in;
//root：子树的根,start:子树序列的起始点，end:子树序列的结束点
Tree Build(int root,int start,int end){
    if(start > end) return NULL;
    //生成子树的根节点
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node -> data = pre[root];
    int pos = start;
    //查找先序的根在中序的位置，将中序分成左子树和右子树两部分
    while(pre[root] != in[pos])
        pos++;
    //建立左子树
    node -> left = Build(root + 1,start,pos - 1);
    //建立右子树
    node -> right = Build(root + pos - start + 1,pos + 1, end);
    //返回根结点
    return node;
}
//递归求解树的高度
int GetHeight(Tree t){
    if(t == NULL)   return 0;
    return max(GetHeight(t -> left),GetHeight(t -> right)) + 1;
}
int main() {
    cin >> n >> pre >> in;
    Tree t = Build(0,0,pre.size() - 1);
    cout << GetHeight(t) << endl;
    return 0;
}