求二叉树的深度
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描写叙述
已知一颗二叉树的中序遍历序列和后序遍历序列，求二叉树的深度。
输入
输入数据有多组，输入T，代表有T组数据。每组数据包含两个长度小于50的字符串。第一个字符串表示二叉树的中序遍历，第二个表示二叉树的后序遍历。
输出
输出二叉树的深度。
演示样例输入
2 dbgeafc dgebfca lnixu linux
演示样例输出
4
3
慢慢来
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
typedef struct node
{
char data;
node *lch,*rch;
}btree,*bt;
char post[55],ins[55];
void build(bt &T,char *ins,char *post,int n) //依据后序和中序重建二叉树
{
if(n<=0) T=NULL;
else
{
int k=strchr(ins,post[n-1])-ins;
T=new btree;
T->data=post[n-1];
build(T->lch,ins,post,k);
build(T->rch,ins+k+1,post+k,n-k-1);
}
}
int deep(bt T)
{
int dep=0;
if(!T) return dep;
int nl=deep(T->lch);
int nr=deep(T->rch);
return (nl>nr?nl:nr)+1;
}
int main()
{
bt root;
int n;
cin>>n;
getchar();
while(n--)
{
cin>>ins>>post;
build(root,ins,post,strlen(ins));
cout<<deep(root)<<endl;
}
return 0;
}