【a403】遍历树问题
2024-10-08 03:00:05
Time Limit: 1 second
Memory Limit: 32 MB
【问题描述】
我们都很熟悉二叉树的前序、中序、后序遍历,在数据结构中常提出这样的问题:已知一棵二叉树的前序和中序遍历,求它的后序遍历,相应的,已知一棵二叉树的后序和中序遍历,你也能求出它的前序遍历。然而,给定一棵二叉树的前序和后序遍历,你却不能确定其中序遍历序列,考虑如下图中的几棵二叉树:
所有这些二叉树都有着相同的前序和后序遍历序列,但中序遍历序列却不相同。
【输入格式】
共两行,第一行表示该二叉树的前序遍历结果S1,第二行表示该二叉树的后序遍历结果S2。
【输出格式】
仅一行,输出可能的中序遍历序列的总数,结果不超过长整型数。
【输入样例】
abc
cba
【输出样例】
4
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=a403
【题意】
【题解】
只有那些没有兄弟节点的节点,它们才能够左右转(即当左子树还是当右子树->不会影响前序遍历和后序遍历)
所以答案就是2^(没有兄弟节点的节点个数)
怎么找那些没有兄弟节点的节点?
如下图
对于1这个没有兄弟节点的节点;
则必有:
先序遍历遍历完1之后就是2
而后序遍历,输出2之后就是输出1
(因为1号节点没有兄弟节点,所以递归完2的子树之后,输出2之后就是直接输出1了)
即s1[i]==s2[j]且s1[i-1]==s2[j+1]
就说明找到了一个没有兄弟节点的节点->s1[i-1]
【完整代码】
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define ref(x) scanf("%lf",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 110;
char s1[N],s2[N];
int len1,len2,ans;
void in()
{
scanf("%s",s1+1),scanf("%s",s2+1);
len1 = strlen(s1+1),len2 = strlen(s2+1);
}
void get_ans()
{
rep1(i,2,len1)
rep1(j,1,len2-1)
if (s1[i]==s2[j] && s1[i-1]==s2[j+1])
ans++;
}
void o()
{
printf("%d\n",1<<ans);
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
in();
get_ans();
o();
//printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
最新文章
- Hadoop设置环境变量注意事项
- Unity3d 制作动态Mesh且可以随地面凹凸起伏
- MVC缓存02,使用数据层缓存,添加或修改时让缓存失效
- Mac配置JAVA_HOME
- sublime添加ctags实现代码跳转
- poj 2635 The Embarrassed Cryptographer(数论)
- NOI2011道路修建
- Qt之json解析
- 熟知CDN
- BotVS数字货币现货交易类库
- .meta和模型贴图丢失
- GSS4 - Can you answer these queries IV(线段树懒操作)
- io多路复用(二)
- 搭建高可用的Redis服务,需要注意这些方面!
- [JSOI2018]列队
- js--------1.时间
- Unable to load DLL &#39;SQLite.Interop.dll&#39;: The specified module could not be found. (Exception from HRESULT: 0x8007007E)
- SpringMVC @SessionAttributes 使用
- php操作oracle查询时中文乱码
- 通过loadrunner将http返回response写入文本txt中
热门文章
- 7 种 Javascript 常用设计模式学习笔记
- Elasticsearch 启动需要密码?
- Apache Camel,Spring Boot 实现文件复制,转移 (转)
- spring-cloud-zuul跨域问题解决
- Directx11教程(51) 简单的billboard
- 2019-1-29-jekyll-如何加密博客-防止抓取
- oracle如何看审计的结果
- mysql锁机制之行锁(四)
- SELinux 宽容模式(permissive) 强制模式(enforcing) 关闭(disabled) 几种模式之间的转换
- dva框架简单描述使用