文档章节

sicily 1210 二叉树

Ciel
 Ciel
发布于 2013/01/05 18:42
字数 919
阅读 154
收藏 0

Description

在众多的数据结构中,二叉树是一种特殊而重要的结构,有着广泛的应用。二叉树或者是一个结点,或者有且仅有一个结点为二叉树的根,其余结点被分成两个互不相交的子集,一个作为左子集,另一个作为右子集,每个子集又是一个二叉树。

遍历一棵二叉树就是按某条搜索路径巡访其中每个结点,使得每个结点均被访问一次,而且仅被访问一次。最常使用的有三种遍历的方式:

1.前序遍历:若二叉树为空,则空操作;否则先访问根结点,接着前序遍历左子树,最后再前序遍历右子树。

2.中序遍历:若二叉树为空,则空操作;否则先中序遍历左子树,接着访问根结点,最后再前中遍历右子树。

3.后序遍历:若二叉树为空,则空操作;否则先后序遍历左子树,接着后序遍历右子树,最后再访问根结点。

例如图(1)所示的二叉树:

前序遍历的顺序是ABCD,中序遍历的顺序是CBAD,后序遍历的顺序是CBDA。

对一棵二叉树,如果给出前序遍历和中许遍历的结点访问顺序,那么后序遍历的顺序是唯一确定的,也很方便地求出来。但如果现在只知道前序遍历和后序遍历的顺序,中序遍历的顺序是不确定的,例如:前序遍历的顺序是ABCD,而后序遍历的顺序是CBDA,那么就有两课二叉树满足这样的顺序(见图(1)和图(2))。

现在的问题是给定前序遍历和后序遍历的顺序,要求出总共有多少棵不同形态的二叉树满足这样的遍历顺序。

Input

整个输入有两行,第一行给出前序遍历的访问顺序,第二行给出后序遍历的访问顺序。
二叉树的结点用一个大写字母表示,不会有两个结点标上相同字母。输入数据不包含空格,且保证至少有一棵二叉树符合要求。

Output

输出一个整数,为符合要求的不同形态二叉树的数目。

Sample Input

ABCD
CBDA

Sample Output


2

分析:

可以这么考虑,当且仅当以节点为根的子树(或原树)子节点只有一个,会产生多种解的情况。那么明显,仅仅根据前序和后序遍历的结果,单个的子节点无法确定左右位置。可以判断有n个这样的节点,那么就可能有2^n种生成树。而这样的节点在本题中的明显特征就是,对应前序遍历路径中的特定节点,它的右面相邻的节点和后序遍历中此节点的左面相邻节点相同。最后注意,利用string的成员函数find()可以节省很多时间。

ps:本题还有另外的表示方法,即直接比较对应字符,不过这里采用别人的一种解法,更有意思也更能体会二叉树遍历的特点。

代码:


// Problem#: 1210
// Submission#: 1860874
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
#include <string>
using namespace std;

int main(){
    string str1,str2;
    int re = 1;
    cin >> str1 >> str2;
    int size = str1.size();
    int tmp = size - 1;
    for( int i=1 ; i<size ; i++ ){
        int j = str2.find(str1[i]);
        if( j==tmp-1 ) re *= 2;
        tmp = j;
    }
    cout << re;
    return 0;
}



© 著作权归作者所有

Ciel
粉丝 3
博文 24
码字总数 18532
作品 0
程序员
私信 提问
Oracle 11g R2 ADG 搭建

--============Oracle ADG搭建============== --==========准备阶段========= 1.检查primary为archivelog模式。 select log_mode from v$database; 如果为noarchivelog模式,切换到archivelo......

UltraSQL
2018/07/23
0
0
软件开发者技术交流大会总结篇

软件开发者技术交流活动,是黑房子社区组织的第一期技术交流活动,经验不足,宣传力度不够,很多人由于没能看到通知错过了本次活动。报名人数34人,实到现场28人。后期我们将继续组织类似的技...

济南工作网
2013/12/10
1K
15
setContentView(R.layout.activity_main);报错

package com.example.tcpsocketclient; import android.net.ConnectivityManager; import android.net.NetworkInfo; import android.os.Bundle; //import android.annotation.SuppressLint; ......

桃花园主
2014/03/04
7.8K
8
基于主机的入侵检测系统ossec安装部署

1.ossec服务端安装 解压>>> #tar -zxvf ossec_server.tar.gz #cd ossec 安装>>> #./install.sh agent.conf初始化>>> #touch /var/ossec/etc/shared/agent.conf 服务启动>>> #/var/ossec/bin......

硅谷课堂
2018/07/25
127
0
sicily 1150 简单魔板 sicily 1151 魔板 sicily 1515 魔板C

这三道题目大体相同,只是数据处理方式不同,需要修改的地方很少,因此只以1150为例说明即可。 Description 魔板由8个大小相同方块组成,分别用涂上不同颜色,用1到8的数字表示。 其初始状态...

Ciel
2012/12/15
949
1

没有更多内容

加载失败,请刷新页面

加载更多

开发中常用的正则表达式

为了能够更好地理解如何在C#环境中使用正则表达式,这里整理了一些常用的正则表达式: 罗马数字: string p1 = "^m*(d?c{0,3}|c[dm])" + "(l?x{0,3}|x[lc])(v?i{0,3}|i[vx])$"; string t1 =......

木庄
21分钟前
4
0
【.NET程序打包】VS2019使用Installer Projects打包

C#—使用Installer Projects打包桌面应用程序 前言 打包桌面应用程序实在是一个不常使用的东西,偶尔使用起来经常会忘东忘西的耽误时间,因此,这篇文章多以图片记录过程,也是用于备忘。 下...

_Somuns
26分钟前
4
0
自定义注解,使用动态代理解决网站的字符集编码问题

第1章设置环境 安装操作系统,安装备份(镜像): JDK: 设置环境变量Eclipse:解压即可 Eclipse自身解压目录不包括中文 代码工作空间目录不包括中文Tomcat:解压不要包含中文目录M...

蓝来杯往
30分钟前
4
0
Solr中的字段类型field type

Solr含有多种字段类型,可用的字段类型基本都定义在了包org.apache.solr.schema中,列举如下: 类 说明 BinaryField 二进制数据 BoolField 布尔值,其中’t’/’T’/’1’都是true Collatio...

gantaos
44分钟前
4
0
《JAVA核心知识》学习笔记 (21. JAVA 算法)

21. JAVA 算法

Shingfi
51分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部