还原二叉树(25 分)_7-1 还原二叉树 分数 10 作者 ds课程组 单位 浙江大学 给定一棵二叉树的先序遍历-程序员宅基地

技术标签: 二叉树  

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

输入格式:

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

输出格式:

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

输入样例:

9
ABDFGHIEC
FDHGIBEAC

输出样例:

5

输入:前序遍历,中序遍历

1、寻找树的root,前序遍历的第一节点G就是root。
2、观察前序遍历GDAFEMHZ,知道了G是root,剩下的节点必然在root的左或右子树中的节点。
3、观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树中的节点,G右侧的HMZ必然是root的右子树中的节点,root不在中序遍历的末尾或开始就说明根节点的两颗子树都不为空。
4、观察左子树ADEF,按照前序遍历的顺序来排序为DAFE,因此左子树的根节点为D,并且A是左子树的左子树中的节点,EF是左子树的右子树中的节点。
5、同样的道理,观察右子树节点HMZ,前序为MHZ,因此右子树的根节点为M,左子节点H,右子节点Z。

观察发现,上面的过程是递归的。先找到当前树的根节点,然后划分为左子树,右子树,然后进入左子树重复上面的过程,然后进入右子树重复上面的过程。最后就可以还原一棵树了:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node{
    char elem;
    struct node *left,*right;
};
typedef struct node * Tree;
char in[55],pre[55];
Tree findTree(char in[],char pre[],int length){
    if(length==0) return NULL;
    Tree head=(Tree)malloc(sizeof(struct node));
    head->elem=pre[0];
    int i=0;
    for(i=0;i<length;i++){
        if(in[i]==pre[0]) break;
    }
    head->left=findTree(in,pre+1,i);
    head->right=findTree(in+i+1,pre+i+1,length-i-1);
    return head;
}
int length(Tree head){
    if(head==NULL) return 0;
    int l=length(head->left);
    int r=length(head->right);
    return l>r?l+1:r+1;
}
int main(){
    int n;
    scanf("%d",&n);
    scanf("%s%s",pre,in);
    Tree head=(Tree)malloc(sizeof(struct node));
    head=findTree(in,pre,n);
    printf("%d\n",length(head));
return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/islittlehappy/article/details/78501134

智能推荐

C#通过modbus协议实时更新&nbsp;to…_modbus readline-程序员宅基地

文章浏览阅读1.6k次,点赞2次,收藏2次。tos的显示屏显示界面" TITLE="C#通过modbus协议实时更新 tos的显示屏显示界面" />tos的显示屏显示界面" TITLE="C#通过modbus协议实时更新 tos的显示屏显示界面" />Keil部分代码#include"Include.h" #include"Tools.h" void GetLockCode(uint8 *Buf)tos的显示屏显示界_modbus readline

IOS 内存分配、内存结构、堆栈、静态存储区_ios bbs区 静态区-程序员宅基地

文章浏览阅读4.5k次。IOS 内存分配、内存结构、堆栈、静态存储区_ios bbs区 静态区

python使用ddddocr识别验证码,解决Microsoft visual C++ Redistributable for visual studio 2019 not installed_使用ddocr识别验证码闪退-程序员宅基地

文章浏览阅读1.5k次。使用第三方python库ddddocrimport ddddocr运行程序,报错原来是缺少运行环境,接下来下载并安装该运行环境再次运行python程序,可正常运行_使用ddocr识别验证码闪退

android 视频处理60帧,如何导出60帧视频,让视频画面流畅无比-程序员宅基地

文章浏览阅读1.1k次。原标题:如何导出60帧视频,让视频画面流畅无比随着技术的发展,60帧视频被广泛应用,但由于一些剪辑软件不支持导出60帧视频,不能满足广大视频制作者的需求。如果想要导出60帧视频,让视频画面流畅无比,可以用爱剪辑软件制作!今天,就教大家用爱剪辑软件快速导出60帧视频!爱剪辑官网:www.aijianji.com 一、新建4K超高清视频正常情况下60帧视频对视频清晰度要求较高。因此,在电脑端打开爱剪辑..._davinci resolve导出不了60帧

openwrt LEDE 更改默认固件大小_openwrt编译 减小体积-程序员宅基地

文章浏览阅读1w次,点赞2次,收藏3次。编译 MTK7628 固件时,增加了 PHP 和 nginx 服务,发现固件不出来,经过检查,发现默认的大小为 4M,然而,开发板的 flash 为 32M ,感觉太浪费了。。。经过搜索。。。发现是可以更改 flash固件大小的。..._openwrt编译 减小体积

Java基础之if语句案例_java if语句的经典例子-程序员宅基地

文章浏览阅读5.6k次,点赞3次,收藏8次。/* 从键盘输入小明的期末考试成绩 当成绩为100分时,奖励一辆BMW; 当成绩为(80,99]时,奖励一台8848; 当成绩为[60,80]时,奖励一本从入门到精通只需33天; 其它时,暴打一顿! */import java.util.Scanner;public class Scanner05{ public static void main(String[] args_java if语句的经典例子

随便推点

C++设计模式之装饰模式_虚函数实现装饰模式-程序员宅基地

文章浏览阅读876次。C++设计模式之装饰模式 动态地给一个对象增加一些额外的职责,就增加对象的功能来说,装饰模式比生成子类更为灵活。装饰模式是一种对象结构模式。一、缘由我们常常通过继承的方式来对一个既有的类进行功能添加,但继承方式有显著的局限性,因为继承具有侵入性继承是一种is a的关系,具有强耦合性,难以复用代码。例如在窗口控件当中,要增加新的功能如增加滚动条,增加背景图片,通过继承的方式来增加新的功能,_虚函数实现装饰模式

AI绘画室内设计提示词大全(持续更新)_ai建模室内完整的关键词-程序员宅基地

文章浏览阅读1.9k次,点赞30次,收藏25次。当你开始使用AI绘画进行室内设计(interior design)时,选择合适的提示词和关键概念对于成功构思和实现你的设计理念至关重要。以下是一些关于室内设计的提示词,涵盖了空间类型、设计风格、光线效果、布局规划、材料类型以及其他要求的详细说明。本文将长期进行更新,欢迎关注。文中所涉及的内容也可在RdFast智能创作机器人小程序中即刻进行体验,包括AI素材、AI文案、AI编辑、AI绘画、AI室内设计和AI头像设计等。本文主要包括以下部分,后续将持续更新。(1)正向提示词 prompt。_ai建模室内完整的关键词

学习使用solr(一),solr和tomcat的配置及数据库中表的全量索引(上)-程序员宅基地

文章浏览阅读86次。 最近在学习solr,碰到了不少问题。我学习solr的第一期目标是能把solr和tomcat搞在一起,并且可以对数据库中的一张表建立一个全索引。 第一步,将solr部署进tomcat。 我有下载好的tomcat6.0与solr-3.6.2,我要使用的服务器系统是linux,具体不清楚是什么版本的linux。把solr部署在tomcat上的步骤完全按照..._solr 索引tomcat

键盘上每个键作用!!! (史上最全的) -程序员宅基地

文章浏览阅读169次。F1帮助 F2改名 F3搜索 F4地址 F5刷新 F6切换 F10菜单 CTRL+A全选 CTRL+C复制 CTRL+X剪切 CTRL+V粘贴 CTRL+Z撤消 CTRL+O打开 SHIFT+DELETE永久删除 DELETE删除 ALT+ENTER属性 ALT+F4关闭 CTRL+F4关闭 ALT+TAB切换 ALT+ESC切换 ALT+空格键窗口菜单 CTRL+ESC开始菜单 拖动某一项时按C

Android--Handler的内存泄漏原因及解决方法_为什么静态类能避免handler内存泄漏-程序员宅基地

文章浏览阅读3.3k次。一、如何造成内存泄漏:1、主线程的Looper对象会伴随该应用程序的整个生命周期2、Java里,非静态内部类和匿名类都会潜在引用它们所属的外部类发送的延迟空消息(EmptyMessageDelayed)后、消息处理被前,该消息会一直保存在主线程的消息队列里持续时间,在持续时间里,该消息内部持有对handler的引用,由于handler属于非静态内部类,所以又持有对其外部类(即MainA_为什么静态类能避免handler内存泄漏

2. avr定时器/计数器0 --TC0 --快速PWM输出 (比较输出--快速PWM模式)_t/c0实现pwm-程序员宅基地

文章浏览阅读1.7k次。PWM:脉冲宽度调制,图中T为脉冲周期,t为高电平时间,t与T的比值t/T称为占空比,脉宽调制指的是调整t的大小,即改变脉冲的占空比,占空比值越大,输出的电压越高。改变占空比就改变输出的电压,常用于实现D/A,调节电压或电流,改变电动机的转速等。 快速PWM模式:它的计数方式是TCNT0由0开始计数到255式,计数加1返回到0,然后继续加1计数,相对于相位PWM修正模式(由0计数到25_t/c0实现pwm