还原二叉树（25 分）-程序员宅基地

技术标签：二叉树

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

输入格式:

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

输出格式:

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

输入样例:

9
ABDFGHIEC
FDHGIBEAC

输出样例:

输入：前序遍历，中序遍历

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;
}

本文链接：https://blog.csdn.net/islittlehappy/article/details/78501134

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

一个基于 osip 库的 UAC 和 UAS 的代码整理(转)_uas_do_inquiry-程序员宅基地

从网上搞了一个基于osip 库的 SIP 协议的简单的 UAC 代理客户端和 UAS 代理服务器端，并进行了编译连接，代码整理后如下： ----------- UAC 代理客户端的代码整理 ---------------/** * 一个使用了 osip 和 eXosip 库的 UAC 代理客户端的演示程序 * * - 只是简单的演示了使用了 osip 和 ..._uas_do_inquiry

数据分析学习——数据清洗-程序员宅基地

学习这么长时间的数据分析，却没有好好的做个总结，前段时间面试的时候，有面试官提问，如何做数据清洗。但由于平时缺少总结，回答的不是很好。于是博主决定好好地学习总结一番。数据清洗主要针对一下几类脏数据：1）缺失值2）异常值3）重复值缺失值一、数据为什么会缺失数据缺失主要分为两大类：有意的：有些数据特征在设计的时候考虑会有缺失值的情况，而缺失数据往往不代表真的缺失，而是另有含义。比如...

delphi7 中编辑按钮 RzButtonEdit 使用说明-程序员宅基地

1.当控件获取鼠标焦点时，显示如下：2.当控件失去鼠标焦点时，显示如下：3.这种效果有点类似于QQ登陆界面，大家没事的时候可以试一试，与QQ登陆界面不同点在于：这个控件获取鼠标焦点时，控件里面的那个按钮也变蓝色，但是腾讯QQ是不变色的。4.RzButtonEdit具体使用如下：属性：ButtonKind --》用于选择控件里面那个按钮的形状，可以选择很多。Fla_buttonedit

浅谈红黑树的添加删除操作-程序员宅基地

红黑树的性质（牢记） 1、每个结点的颜色只能是红色或黑色。 2、根结点必须是黑色的。 3、每个叶子结点都带有两个空的黑色结点（被称为黑哨兵null），如果一个结点n的只有一个左孩子，那么n的右孩子是一个黑哨兵；如果结点n只有一个右孩子，那么n的左孩子是一个黑哨兵。 4、如果一个结点是红的，则它的两个儿子都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。 5、从任何一个结点到其子孙叶

oracle expdp导出指定表的部分数据_oracle expdp 某个表的某些记录-程序员宅基地

from http://blog.csdn.net/zhrzhl/article/details/12038583oracle expdp导出指定表的部分数据指定部分表数据导出[oracle@oratest ~]$ expdp oracle/oracle@oratest dumpfile=20130826.dmp directory=dpdump tables=_oracle expdp 某个表的某些记录

信号量sem_init,sem_wait,sem_post-程序员宅基地

https://youth.blog.csdn.net/article/details/78318932?utm_medium=distribute.pc_relevant.none-task-blog-OPENSEARCH-1.control&dist_request_id=&depth_1-utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-1.control_信号量sem_init,sem_wait,sem_post

随便推点

安装VirtualBox_virtualbox.box-程序员宅基地

安装VirtualBox 和 vagrant 1、下载virtualbox包https://www.virtualbox.org/wiki/Downloads 2、下载vagrant 包 https://www.vagrantup.com/downloads.html 3、以上两个工具直接安装（vagrant可以使用终端命令直接安装） 4、在终端输入vagrant测试是否可以使用（这是一个虚拟机管理工具） 5、下载镜像 http://cloud.centos.org/centos/7/v._virtualbox.box