题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度\le 8≤8)。
输入输出格式
输入格式:
22行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序排列。
输出格式:
11行,表示一棵二叉树的先序。
输入输出样例
BADC
BDCA
ABCD 虽然这是一道我做过第三次类似的题目的题了 优化:
可以不用print函数来打印
直接在建树里面打印
#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define inf 2147483647
#define N 500000+50
int zhong[N];
int hou[N]; void build(int l,int r,int l2,int r2)
{
if(l>r||l2>r2)return ;
int root=hou[r2];
int p=l;
while(zhong[p]!=root)p++;
int cnt=p-l;
printf("%c",root);
build( l, p-,l2,l2+cnt-);
build(p+,r,l2+cnt,r2-); }
int main()
{
char s[];
RS(s);
rep(i,,strlen(s))
zhong[i]=s[i];
RS(s);
rep(i,,strlen(s))
hou[i]=s[i];
int len=strlen(s);
build(,len-,,len-);
}
大佬的做法
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
void beford(string in,string after){
if (in.size()>){
char ch=after[after.size()-];
cout<<ch;//找根输出
int k=in.find(ch);
beford(in.substr(,k),after.substr(,k));
beford(in.substr(k+),after.substr(k,in.size()-k-));//递归左右子树;
}
}
int main(){
string inord,aftord;
cin>>inord;cin>>aftord;//读入
beford(inord,aftord);cout<<endl;
return ;
}
题目描述
输入一串二叉树,用遍历前序打出。
输入输出格式
输入格式:
第一行为二叉树的节点数n。(n \leq 26n≤26)
后面n行,每一个字母为节点,后两个字母分别为其左右儿子。
空节点用*表示
输出格式:
前序排列的二叉树
输入输出样例
6
abc
bdi
cj*
d**
i**
j**
abdicj 沦落为做水题了 真是尴尬
#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define inf 2147483647
#define N 200
int l[N];
int r[N];
int vis[N];
int cnt[N];
void print(int x)
{
if(!x)return ;
if(x=='*')return ;
printf("%c",x);
print(l[x]);
print(r[x]);
return ;
}
int main()
{
int n;
RI(n);
char s[];
while(n--)
{
RS(s);
vis[s[]]=;
vis[s[]]=;
vis[s[]]=;
if(s[]!='*')
{
l[s[]]=s[];
cnt[s[]]++;
}
if(s[]!='*')
{
r[s[]]=s[];
cnt[s[]]++;
}
}
int root;
rep(i,'a','z')
if(vis[i]&&!cnt[i])
{
root=i;break;
}
print(root);
}
P1030 求先序排列 P1305 新二叉树的更多相关文章
-
洛谷:P1087 FBI树 P1030 求先序排列 P1305 新二叉树
至于为啥把这三个题放到一起,大概是因为洛谷的试炼场吧,三道树的水题,首先要理解 先序中序后序遍历方法. fbi树由于数量小,在递归每个区间时,暴力跑一遍区间里的数,看看是否有0和1.至于递归的方法,二 ...
-
二叉树的遍历 &;【NOIP2001普及组】&; 洛谷 P1030 求先序排列
题目链接 https://www.luogu.org/problemnew/show/P1030 模板题 先讲一下二叉树的遍历 二叉树的遍历 分类 性质 求法 分为三类: 先序遍历(PreOrder) ...
-
P1030 求先序排列 /// 二叉树的遍历
题目大意: 给一棵树的中序排列 后序排列,求这棵树的先序排列 https://www.luogu.org/problemnew/show/P1030 二叉树的四种遍历解说 几种遍历的递归实现 后序排列 ...
-
洛谷 P1030 求先序排列 Label:None
题目描述 给出一棵二叉树的中序与后序排列.求出它的先序排列.(约定树结点用不同的大写字母表示,长度<=8). 输入输出格式 输入格式: 2行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序 ...
-
洛谷P1030求先序排列
题目描述 给出一棵二叉树的中序与后序排列.求出它的先序排列.(约定树结点用不同的大写字母表示,长度≤8. 输入输出格式 输入格式: 2行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序排列. 输 ...
-
P1030 求先序排列
题目描述 给出一棵二叉树的中序与后序排列.求出它的先序排列.(约定树结点用不同的大写字母表示,长度<=8). 输入输出格式 输入格式: 2行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序 ...
-
洛谷 P1030 求先序排列
题目描述 给出一棵二叉树的中序与后序排列.求出它的先序排列.(约定树结点用不同的大写字母表示,长度<=8). 输入输出格式 输入格式: 2行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序 ...
-
洛谷——P1030 求先序排列
https://www.luogu.org/problem/show?pid=1030#sub 题目描述 给出一棵二叉树的中序与后序排列.求出它的先序排列.(约定树结点用不同的大写字母表示,长度< ...
-
P1030 求先序排列 (一个非常棒的写法)
理论正确就是真正的正确,误... 就是找嘛,找到每一个对应字符,然后对应的左右子树的区间,然后就可以了. #include <bits/stdc++.h> using namespace ...
随机推荐
-
js中substr,substring,indexOf,lastIndexOf的用法小结
第一组:str.substr(start,length) 和 str.substring(start,end) 定义: str.substr(start,length) substr(start,le ...
-
DOCTYPE 中xhtml 1.0和 html 4.01区别分析
前者相对于后者有以下特性: 1.所有的标记都都要闭合 所有的标记都要闭合,如果是单独不成对的标签,在标签最后加一个"/"来关闭它.例如: <h6>close tag & ...
-
Objective-C 学习笔记(Day 1)
-------------------------------------------- Hello World //引入头文件 //c中的引入头文件的方式 //#include <stdio. ...
-
Linux记录-sftp上传大文件
1.Alt +P 进入sftp会话 2.pwd显示linux目录 lpwd显示windows目录 3.lcd切换windows目录 cd切换linux目录 4.put上传 5.get下载 6.help ...
-
ServiceHub.DataWarehouseHost.exe内存泄漏问题的处理
Visual Studio 2017的15.2版本在debug应用程序时,ServiceHub.DataWarehouseHost.exe会出现严重的内存泄漏的问题,一个小时左右,内存耗了将近8GB. ...
-
3. 原子变量-CAS算法
1. 是什么 ? 2. CAS算法模拟 package com.gf.demo03; public class TestCompareAndSwap { public static void main ...
-
web窗体之四则运算
1,计算方法: namespace ASP.NET { public class JiSuan { public int S; public int Result { get { return S; ...
-
1003 我要通过!| PAT (Basic Level) Practice
1003 我要通过! (20 分) "答案正确"是自动判题系统给出的最令人欢喜的回复.本题属于 PAT 的"答案正确"大派送 -- 只要读入的字符串满足下列条件 ...
-
dp之混合背包poj1742(推荐)
题意:给你价值为a1,a2.....的货币,每种有c1,c2.......个,求这些货币所能组成的价值小于等于m有多少个..... 思路:很像一道多重背包题?那我一开始的确是用多重背包的思路编写的.. ...
-
sublime3配置java开发环境
链接:http://www.jianshu.com/p/48a524a4f63c 或者:http://www.jianshu.com/p/9d167c4c4feb 侵权删!