codevs 1029 遍历问题
2024-09-25 05:06:19
题目描述 Description
我们都很熟悉二叉树的前序、中序、后序遍历,在数据结构中常提出这样的问题:已知一棵二叉树的前序和中序遍历,求它的后序遍历,相应的,已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序,你却不能确定其中序遍历序列,考虑如下图中的几棵二叉树:
所有这些二叉树都有着相同的前序遍历和后序遍历,但中序遍历却不相同。
输入描述 Input Description
输入文件共2行,第一行表示该树的前序遍历结果,第二行表示该树的后序遍历结果。输入的字符集合为{a-z},长度不超过26。
输出描述 Output Description
输出文件只包含一个不超过长整型的整数,表示可能的中序遍历序列的总数。
样例输入 Sample Input
abc
cba
样例输出 Sample Output
4
只有一个孩子节点,才会造成中序遍历的不同
而只有一个孩子的节点,他和他的孩子在先序遍历、后序遍历中相反
所以ans=2^只有一个子节点的点的总数
#include<cstdio>
#include<cstring>
using namespace std;
char s1[],s2[];
int ans;
int main()
{
scanf("%s%s",s1,s2);
int len1=strlen(s1),len2=strlen(s2);
for(int i=;i<len1-;i++)
for(int j=;j<len2;j++)
if(s1[i]==s2[j]&&s1[i+]==s2[j-])
ans++;
printf("%d",(<<ans));
}
最新文章
- Hibernate 系列 学习笔记 目录 (持续更新...)
- sql评估期已过如何解决该问题
- 【转】给Windows + Apache 2.2 + PHP 5.3 安装PHP性能测试工具 xhprof
- delphi override、overload、reintroduce的区别-0613.txt
- Android控件系列之RadioButton&;RadioGroup(转)
- .NET中的Action及Func泛型委托
- java 异常2
- Linux环境下Python的安装过程
- Android SeekBar实现音量调节
- cat主要有三大功能
- fitnesse - 安装部署
- Java垃圾回收(整理)
- 小程序学习(冒泡,快速创建文件,以及tarbar)
- openssl内核升级
- go语言学习--go中的map切片
- showdoc 开源在线api&;&;技术文档管理工具
- NET Core Kestrel部署HTTPS
- C++ 备忘录 (1)
- 如何学习mybatis
- 使用cJSON库解析JSON