7-1 还原二叉树

分数 25

全屏浏览题目

切换布局

作者 DS课程组

单位 浙江大学

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

输入格式:

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

输出格式:

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

输入样例:

9
ABDFGHIEC
FDHGIBEAC

输出样例:

5

代码：

#include <stdio.h>
char Str1[55];
char Str2[55];

int Height(int num1,int num2,int lenth,int h)
{
    if(lenth ==0)
        return h-1;
    int len =0;
    while(1)
    {
        if(Str2[num2+len] == Str1[num1])
            break;
        len++;
    }
    int h1 = Height(num1+1,num2,len,h+1);
    int h2 = Height(num1+len+1,num2+len+1,lenth-1-len,h+1);
    return h1>h2?h1:h2;
}

int main()
{
    int n;
    scanf("%d %s %s",&n,Str1,Str2);
    printf("%d",Height(0,0,n,1));
    return 0;
}