求二叉树的深度
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)); } }
转载于:https://www.cnblogs.com/CCCrunner/p/6444637.html
相关资源：JAVA上百实例源码以及开源项目
