搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > ACM比赛整理 > 7-23 还原二叉树 (25分)

7-23 还原二叉树 (25分)

ACM比赛整理 2021-01-14

7-23 还原二叉树 (25分)


给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。

输入格式:

输入首先给出正整数N(50),为树中结点总数。下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区别大小写)的字符串。

输出格式:

输出为一个整数,即该二叉树的高度。

输入样例:

9
ABDFGHIEC
FDHGIBEAC

输出样例:

5


代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

struct node {
char data;
node* lchild;
node* rchild;
};
int n;
char pre[100], in[100];

//当前先序序列区间为[preL, preR], 中序序列区间为[inL, inR], 返回根结点地址
node* create(int preL, int preR, int inL, int inR)
{
if(preL > preR) //先序序列长度小于等于0时,直接返回
return NULL;

node* root = new node; //新建一个新的结点,用来存放当前二叉树的根结点
root->data = pre[preL]; //新结点的数据域为根结点的值
int k;
for(k = inL; k <= inR; k++)
if(in[k] == pre[preL]) //在中序序列中找到in[k]==pre[L]的结点
break;

int numLeft = k-inL; //左子树的结点个数

//左子树的先序区间为[preL+1,preL+numLeft], 中序区间为[inL,k-1]
//返回左子树的根结点地址,赋值给root的左指针
root->lchild = create(preL+1, preL+numLeft, inL, k-1);

//右子树的先序区间为[preL+numLeft+1,preR], 中序区间为[k+1,inR]
//返回右子树的根结点地址,赋值给root的右指针
root->rchild = create(preL+numLeft+1 , preR, k+1, inR);

return root; //返回根结点地址
}

int TreeDepth(node* T)
{
if(T==NULL) return 0;
int LD = TreeDepth(T->lchild);
int RD = TreeDepth(T->rchild);
return (LD>RD?LD:RD)+1;
}

int main()
{
scanf("%d", &n);
scanf("%s", pre);
int len1 = strlen(pre);
scanf("%s", in);
int len2 = strlen(in);

node* T = create(0, len1-1, 0, len2-1);
printf("%d\n", TreeDepth(T));
return 0;
}


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《7-23 还原二叉树 (25分)》的版权归原作者「ACM比赛整理」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注ACM比赛整理微信公众号

ACM比赛整理微信公众号:gh_26b2b69d8953

ACM比赛整理

手机扫描上方二维码即可关注ACM比赛整理微信公众号

ACM比赛整理最新文章

精品公众号随机推荐