求二叉树的深度

题目描述

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

输入

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

输出

输出二叉树的深度。

示例输入

2 dbgeafc dgebfca lnixu linux

示例输出

4 #include<stdio.h> #include<string.h> #include<stdlib.h> typedef char telemtype; typedef char status; typedef struct BiTNode {     telemtype data;     struct BiTNode *lchild,*rchild; }*BiTree; void BinaryTree(BiTree &T,char aft[],char mid[],int fs,int ms,int length) //fs:后序序列起始位置；ms：中序序列起始位置； {     if(length==0) T=NULL;//树后序序列的深度为0，则树空     else     {         int k=0;         int n=strlen(mid);         for(k=0;k<n;k++)//找到根节点在中序序列中的位置，用以划分左右子树         {             if(mid[k]==aft[fs+length-1])//后序序列最后一个节点是根节点；                 break;         }         T=new BiTNode;         if(!T) exit(0);         T->data=aft[fs+length-1];//根节点的赋值；         if(k==ms) T->lchild=NULL;//若仅有一个元素，则此结点左子树为空         else BinaryTree(T->lchild,aft,mid,fs,ms,k-ms);         if(k==ms+length-1) T->rchild=NULL;//若仅有一个元素，则此结点右子树为空         else  BinaryTree(T->rchild,aft,mid,fs+k-ms,k+1,length-(k-ms)-1);     } } int depth(BiTree &T)//树的深度函数； {     int lth,rth;     if(!T) return 0;     else     {         lth=depth(T->lchild);        rth=depth(T->rchild);        if(lth>rth)         return lth+1;        else         return rth+1;     } } int main() {     char aft[55],mid[55];     int n;     BiTree T;     scanf("%d",&n);     while(n--)     {         scanf("%s\n%s",mid,aft);         int length=strlen(aft);         BinaryTree(T,aft,mid,0,0,length);//由后序序列和中序序列求前序序列；         printf("%d\n",depth(T));     } }