sdut原题链接
求二叉树的深度 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 已知一颗二叉树的中序遍历序列和后序遍历序列，求二叉树的深度。
Input 输入数据有多组，输入T，代表有T组数据。每组数据包括两个长度小于50的字符串，第一个字符串表示二叉树的中序遍历，第二个表示二叉树的后序遍历。
Output 输出二叉树的深度。
Example Input 2 dbgeafc dgebfca lnixu linux
Example Output 4 3
Hint
Author
以下为accepted代码
#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct node{ char date; struct node *left; struct node *right;}BinTree;BinTree *root;char st1[54], st2[54];BinTree * get_build(int len, char *st1, char *st2)//建立二叉树函数{ if(len <= 0) return NULL; BinTree *root; root = (BinTree *)malloc(sizeof(BinTree)); root->date = st2[len-1];//寻找树节点，新的树节点为后序遍历st2的最后一个 int p = strchr(st1, st2[len-1]) - st1;//寻找新的树节点在中序遍历st1中的位置 root->left = get_build(p, st1, st2);//（左子树的长度，左子树在中序遍历st1中的开始位置，左子树在后序遍历st2中的开始位置） root->right = get_build(len-p-1, st1+p+1, st2+p);//（右子树的长度，右子树在中序遍历st1中的开始位置，右子树在后序遍历st2中的开始位置） return root;}int get_hight(BinTree *root)//计算树的深度函数{ if(root) { int HL, HR, MAXH; HL = get_hight(root->left); HR = get_hight(root->right); MAXH = HL>HR? HL: HR; return (MAXH+1); } else return 0;}int main(){ int T, len, y; scanf("%d", &T); while(T--) { scanf("%s %s", st1, st2); len = strlen(st1); root = get_build(len, st1, st2);//调用建立二叉树函数 y = get_hight(root);//调用计算二叉树深度函数 printf("%d/n", y); } return 0;}/***************************************************User name: jk160630Result: AcceptedTake time: 0msTake Memory: 108KBSubmit time: 2017-02-07 20:59:17****************************************************/新闻热点
疑难解答
