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

输入格式:

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

输出格式:

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

输入样例:

1
2
3
9
ABDFGHIEC
FDHGIBEAC

输出样例:

1
5

思路

首先根据先序和中序序列还原二叉树。然后求树的高度。

还原二叉树的难点应该是在确定递归还原二叉树的左右子树时的参数上。如果用个数确定的话容易乱，可以采用差值的方法。比如此题里面，用ij对应pre，lr对用mid，用idx表示root节点在mid中的位置。当还原左子树时，mid序列的位置很好写，就是l->idx-1，pre肯定是从i+1->某一个位置x，可以利用差值 x-(i+1)=idx-1-l，很方便的得到x=idx-l+i。右子树的边界如果确定复杂的话也可以用这个方法。

代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <string>

using namespace std;

string pre,mid;//前序 和 中序 序列
int cnt=1;//nodes[0]已经分配给root了

struct Node
{
    char data;
    int l,r;
}nodes[55];

//还原二叉树 i j 对应pre l r 对应 mid
void rebuild(int i,int j,int l,int r,int root)
{
    nodes[root].data=pre[i];
    
    //在中序遍历中找到根 
    int idx;
    for(idx=l;idx<=r;++idx)
        if(mid[idx]==pre[i])
            break;
    //idx 现在指向 mid中的根
    //从 l->mid-1 是左子树里的节点 从mid+1->r是右子树的节点
    
    if(idx!=l)//有左子树
        rebuild(i+1,idx-l+i,l,idx-1,nodes[root].l=cnt++);//idx-1-l=x-(i+1) x=idx-l+i
    else 
       nodes[root].l=-1;
    
    if(idx!=r)
        rebuild(idx-l+i+1,j,idx+1,r,nodes[root].r=cnt++);
    else 
        nodes[root].r=-1;
}


int get_height(int root)
{
    if(root==-1)
        return 0;
    else 
        return max(get_height(nodes[root].l),get_height(nodes[root].r))+1;
}

int main()
{
    int N;
    
    cin>>N>>pre>>mid;
    
    rebuild(0,N-1,0,N-1,0);
    
    cout<<get_height(0);
    
    return 0;
}