数据结构已知中后序列求前序及深度

妖狐艹你老母 2022-07-19 02:42 100阅读 0赞

## 求二叉树的深度 ##

####  ####

#### 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<string.h> #include<stdlib.h> #include<malloc.h> int t; int len; char mid[1000],last[1000]; struct node { char data; struct node *lc,*rc; }; //还原二叉树法一 /*struct node *creat(char mid[],char last[],int len) { if(len==0) { return NULL; } struct node *root; root=(struct node *)malloc(sizeof(struct node)); root->data=last[len-1]; char *p; for(p=mid;p!=NULL;p++) { if(*p==last[len-1]) break; } int t=p-mid; root->lc=creat(mid,last,t); root->rc=creat(p+1,last+t,len-t-1); return root; };*/ //还原二叉树法二 struct node *creat(char mid[],char last[],int len) { if(len==0) { return NULL; } struct node *root; root=(struct node *)malloc(sizeof(struct node)); root->data=last[len-1]; int i; for(i=0;i<len;i++)//从中序中查找与前序中树根节点相同的值 { if(mid[i]==last[len-1]) break; } //通过递归调用查找子数的树根 root->lc=creat(mid,last,i);//无限递归调用左子树 root->rc=creat(mid+i+1,last+i,len-i-1);//无限递归调用右子树 return root; }; //前序输出 void fristput(struct node *root) { if(root!=NULL) { printf("%c",root->data); fristput(root->lc); fristput(root->rc); } } //深度求解 int depth(struct node *root) { if(root==NULL) { return 0; } int ldepth,rdepth; ldepth=depth(root->lc); rdepth=depth(root->rc); if(ldepth>rdepth) { return ldepth+1; } else { return rdepth+1; } } int main() { int n; scanf("%d",&n); while(n--) { scanf("%s %s",&mid,&last); len=strlen(last); t=0; struct node *root; root=creat(mid,last,len); fristput(root); t=depth(root); printf("%d\n",t); } return 0; }`         ##