还原二叉树(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

智能推荐

java函数重载返回值,论程序员成长的正确姿势_java 重栽函数返回值-程序员宅基地

文章浏览阅读68次。如何提升自己的实力?Step 1:梳理自己的知识对照下面这份学习大纲,梳理出自己的知识盲区,这份大纲里面的技术点完全对标P7岗的主流技术,因此这是一份很好的知识大纲笔记。Step 2:查漏补缺,夯实基础对照上面分享的学习路线梳理完自己的知识点后,就能够很清楚的知道自己的知识盲区,这样才能更加高效的学习,更快的往中高级程序员发展Java核心技术:(涵盖了JVM、并发编程、网络、分布式、微服务、数据库、数据结构与算法等等技术知识)Spring高级源码:Spring的重要性应该不用再多_java 重栽函数返回值

右侧联系我们html,HTML5 带输入箭头提示框的联系我们表单模板-程序员宅基地

文章浏览阅读1k次。CSS语言:CSSSCSS确定/*source: http://webdesign.tutsplus.com/tutorials/bring-your-forms-up-to-date-with-css3-and-html5-validation--webdesign-4738*//* === Remove input autofocus webkit === */*:focus {outline..._html的页面右侧联系方式怎么

project2016资源管理_学习利用prroject创建资源列表、资源分配,成本分配及运作等,并熟悉各种查看资源任-程序员宅基地

文章浏览阅读8.2k次,点赞5次,收藏41次。在学习过程中我们会感受到project的一系列操作真的很是方便,今天给大家介绍一下project2016中的资源管理部分(1) 创建资源列表、资源分配,成本分配的步骤和结果创建资源列表:打开资源工作表的方法:方法一:首先在甘特图区域右键,会出现如下所示的页面选择“资源分配表”,这样弹出来的页面就是资源分配表方法二:在工具栏中选择“视图”“资源工作表”也会弹出资源工作表页面如下图所示..._学习利用prroject创建资源列表、资源分配,成本分配及运作等,并熟悉各种查看资源任

【Linux操作系统】--进程间通信--匿名管道和命名管道_操作系统命名管道通信-程序员宅基地

文章浏览阅读1.5k次,点赞2次,收藏4次。进程间通信介绍进程间通信目的进程间通信发展匿名管道什么是管道站在文件描述符角度-深度理解管道匿名管道建立信道开始操作-管道基本特性 总结:命名管道命名管道创建一个命名管道编写一个命名管道创建管道服务器端读取客户端client写入 写端业务逻辑拓展功能总结_操作系统命名管道通信

Matlab画时间序列图/绘制子图-程序员宅基地

文章浏览阅读1.8w次,点赞4次,收藏45次。matlab入门阶段,需要用matlab画时间序列图,比较简单,可能以后看起来会感觉很小儿科,但是一些细节上的操作害怕有些遗漏,特此记录。1、可以利用excel打开时间序列文件,截取需要操作的数据所在的区域,其实在matlab中也可以截取。2、在Input Data之后,将output Type修改一下3、Import Selection即可。4、因为输出的是列向量,所以要在下..._matlab画时序图

Android Studio使用Google Flutter完整教程 【0】_android flutter教程-程序员宅基地

文章浏览阅读490次。转载自:https://blog.csdn.net/gfg156196/article/details/81118368 一套代码 iOS、Android 两端运行,Google Flutter 实在太强大。。“Flutter 可帮助你更容易、更快速的开发界面美观的移动应用。” — — Google Flutter 使用的是 Google 自己开发的网络编程语言——Dart 语..._android flutter教程

随便推点

【校内互测】回文词_tail++ head-1-程序员宅基地

文章浏览阅读684次。痛苦是人类的属性,它能证明你还活着。_tail++ head-1

P1618 三连击(升级版)洛谷 (C++) (NEXT_PERMUTATION)_三连击升级版c++-程序员宅基地

文章浏览阅读465次。与并不是升级版的版本一样的解法…利用STL中的 next_permutation 全排列算法可轻松得到答案注意判断的更改,详情见代码#include &lt;iostream&gt;#include &lt;vector&gt;#include &lt;algorithm&gt;using namespace std ;int main(){ int a , b , ..._三连击升级版c++

南大计算机学硕调剂,2017年南京大学计算机科学与技术系考研复试名单-程序员宅基地

文章浏览阅读319次。经我校研究生院审核,确定我系复试名单如下。请各位上线考生务必在3月10日17点之前通过电子邮件方式确认参加复试,否则视为放弃。邮件发送至[email protected]。格式为:邮件主题:确认参加学术型/专业学位复试——姓名(考生编号)//具体哪一种复试请根据实际情况邮件内容:考生信息:考生编号、姓名、单科成绩、总分本人确认参加南京大学计算机科学与技术系3月14日至16日的学术型/专业学位..._南京大学计算机李重

GCC编译简单范例_gcc编译案例-程序员宅基地

文章浏览阅读1.6k次。1.单一程序:打印Hello源文件为hello.c无选项编译链接gcc hello.c将hello.c预处理、汇编、编译并链接形成可执行文件。这里未指定输出文件,默认输出为a.out选项 -o-o选项用来指定输出文件的文件名gcc hello.c -o hello选项 -Egcc -E hello.c -o hello.i将hello.c预处理输..._gcc编译案例

linux制作html文档,生成Kernel文档(转换rst为阅读友好的html)-程序员宅基地

文章浏览阅读462次。0x00 Kernal与rstLinux kernal的文档使用rst结构化文本编写,阅读kernal\msm-4.1.4\README文档可知,可以通过make htmldocs生成可读的html那就试一试,果然报错了HOSTCC scripts/basic/fixdepDocumentation/Makefile:24: The 'sphinx-build' command was not ..._linux .rst 转换html

理解box-sizing属性border-box,content-box_当该元素的css属性box-sizing的值分别为content-box和border-box时,该-程序员宅基地

文章浏览阅读2.8w次,点赞27次,收藏55次。普通盒模型与怪异盒模型对比。box-sizing:content-box,box-sizing:border-box;对比。如何使用普通盒模型与怪异盒模型,如何让浏览器只支持标准盒模型。_当该元素的css属性box-sizing的值分别为content-box和border-box时,该元素在浏览

推荐文章

热门文章

相关标签