数据结构实验之二叉树四：还原二叉树 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic PRoblem Description
给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。 Input
输入数据有多组，每组数据第一行输入1个正整数N(1 <= N <= 50)为树中结点总数，随后2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母(区分大小写)的字符串。 Output
输出一个整数，即该二叉树的高度。 Example Input
9 ABDFGHIEC FDHGIBEAC Example Output
5 Hint
大言不惭的说说水题。。虽然做的过程并不一帆风顺
#include <stdio.h>#include <stdlib.h>typedef struct node{ char data; struct node *l,*r;}node;node *create(int len,char *pre,char *in)//老套路了，知道先序和中序搞出整棵树{ int i; node *root; if(len<=0) return NULL; else{ root = (node *)malloc(sizeof(struct node)); char x = pre[0]; root->data = x; for(i=0; i<len; i++){ if(in[i]==x) break; } root->l = create(i,pre+1,in); root->r = create(len-i-1,pre+i+1,in+i+1); } return root;}int deep(node *root)//求深度的话，就看左右子树哪个更深就返回哪个的深度，最后加个1就是整棵树的深度了{ int d = 1; if(root){ int dl = deep(root->l); int dr = deep(root->r); d = dl>dr?dl+1:dr+1; } else return 0;//一定到最后没有左右子树的话要返回0，这样就不会又加1了 return d;}int main(){ int len; char pre[100],in[100]; while(~scanf("%d",&len)){ scanf("%s %s",pre,in); node *root = create(len,pre,in); printf("%d/n",deep(root)); } return 0;}新闻热点
疑难解答
