sdut原题链接
数据结构实验之二叉树四：还原二叉树 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。
Input 输入数据有多组，每组数据第一行输入1个正整数N(1 <= N <= 50)为树中结点总数，随后2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母(区分大小写)的字符串。
Output 输出一个整数，即该二叉树的高度。
Example Input 9 ABDFGHIEC FDHGIBEAC
Example Output 5
Hint
Author xam
以下为accepted代码
#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct node{ char date; struct node *left; struct node *right;}BinTree;BinTree *root;int len;char st1[54], st2[54];BinTree * ans(int len, char *st1, char *st2)//建立二叉树函数{ if(len == 0) return NULL; int i; BinTree *root; root = (BinTree *)malloc(sizeof(BinTree)); root->date = st1[0];//寻找根节点，新的根节点为st1的第一个 for(i = 0; i < len; i++)//寻找新的根节点在中序序列st2中的位置 { if(st2[i] == root->date) break; } root->left = ans(i, st1+1, st2);//（左子树的长度，左子树在st1中的开始位置，左子树在st2中的开始位置） root->right = ans(len-i-1, st1+i+1, st2+i+1);//（右子树的长度，右子树在st1中的开始位置，右子树在st2中的开始位置） return root;}int get_hight(BinTree *root)//计算二叉树的深度函数{ int HL, HR, MAXH; if(root) { HL = get_hight(root->left); HR = get_hight(root->right); MAXH = HL>HR? HL: HR; return (MAXH + 1); } else return 0;}int main(){ int n, y; while(scanf("%d", &n) != EOF) { scanf("%s %s", st1, st2); root = ans(n, st1, st2);//调用建立二叉树函数 y = get_hight(root);//调用计算二叉树的深度函数 printf("%d/n", y); } return 0;}/***************************************************User name: jk160630Result: AcceptedTake time: 0msTake Memory: 116KBSubmit time: 2017-02-07 19:21:23****************************************************/新闻热点
疑难解答
