数据结构实验之二叉树四：（先序中序）还原二叉树
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。
Input
输入数据有多组，每组数据第一行输入1个正整数N(1 <= N <= 50)为树中结点总数，随后2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母(区分大小写)的字符串。
Output
输出一个整数，即该二叉树的高度。
Sample Input
9
ABDFGHIEC
FDHGIBEAC
Sample Output
5
Hint
Source
xam
#include <stdio.h> #include <stdlib.h> #include <string.h> struct node { char data; struct node *lc; struct node *rc; }; char a[101], b[101]; struct node *creat(char a[], char b[], int n) { struct node *root; if(n == 0) { return NULL; } int i; root = (struct node *)malloc(sizeof(struct node)); root->data = a[0]; for(i = 0; i < n; i++) { if(b[i] == a[0]) { break; } } root->lc = creat(a+1,b,i); root->rc = creat(a+1+i, b+1+i, n - 1- i); return root; } int deep(struct node *root) { int d, d1, d2; if(root != NULL) { d1 = deep(root->lc); d2 = deep(root->rc); if(d1 >= d2) { d = d1 + 1; } else { d = d2 + 1; } } else { d = 0; } return d; } int main() { int n, h; while(scanf("%d", &n) != EOF) { struct node *root; scanf("%s %s", a, b); root = creat(a,b,n); h = deep(root); printf("%d\n", h); } return 0; }
