求二叉树的深度

求二叉树的深度

Time Limit: 1000MS Memory limit: 65536K

题目描述

已知一颗二叉树的中序遍历序列和后序遍历序列，求二叉树的深度。

输入

T组数据。每组数据包括两个长度小于<font face="\"Times" new="" roman,="" serif\"="" style="padding: 0px; margin: 0px;">50的字符串，第一个字符串表示二叉树的中序遍历，第二个表示二叉树的后序遍历。

输出

输出二叉树的深度。

示例输入

2
dbgeafc
dgebfca
lnixu
linux

示例输出

4 3

#include<stdio.h>  
 #include<stdlib.h>  
 #include<string.h>  
   
 typedef struct node  
 {  
     char data;  
     struct node *lchild; //左孩子指针
struct node *rchild;  //右孩子指针
 }tree;  
   
 tree *creat(char *pre,char *in,int len) //创建二叉树 
 {  
     tree *p;  
     if(len<=0) //返回上一层函数调用，
{
         p=NULL;  
}
     else  
     {  
         p=(tree *)malloc(sizeof(tree));  //开辟新的内存空间
         p->data=*(pre+len-1); //将pre[]的最后一个字符赋给p->data;
         char *a;  
         for(a=in;a!=NULL;a++)  //查找p->data在in[]字符串的位置
             if(*a==*(pre+len-1))  
{
             break;  
}
         int l=a-in;  //p->data在in[]字符串的位置
         p->lchild=creat(pre,in,l);  
         p->rchild=creat(pre+l,a+1,len-l-1);  
     }  
     return p;  
 }  
   
 int deep(tree *t)  
 {  
     if(!t)  
         return 0;  
     int lchild,rchild;  
     lchild=deep(t->lchild);  
     rchild=deep(t->rchild);  
     return lchild>rchild?lchild+1:rchild+1;  
 }  
   
 int main()  
 {  
     int t;  
     scanf("%d",&t);  
     tree *T;  
     while(t--)  
     {  
         char str1[55],str2[55];  
         scanf("%s%s",str1,str2);  
         int l=strlen(str1);  
         T=creat(str2,str1,l);  
         printf("%d\n",deep(T));  
     }  
 }