P1030 求先序排列 P1305 新二叉树

时间:2023-01-10 19:34:53

  

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度\le 8≤8)。

输入输出格式

输入格式:

22行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序排列。

输出格式:

11行,表示一棵二叉树的先序。

输入输出样例

输入样例#1: 复制
BADC
BDCA
输出样例#1: 复制
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行,每一个字母为节点,后两个字母分别为其左右儿子。

空节点用*表示

输出格式:

前序排列的二叉树

输入输出样例

输入样例#1: 复制
6
abc
bdi
cj*
d**
i**
j**
输出样例#1: 复制
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 新二叉树的更多相关文章

  1. 洛谷:P1087 FBI树 P1030 求先序排列 P1305 新二叉树

    至于为啥把这三个题放到一起,大概是因为洛谷的试炼场吧,三道树的水题,首先要理解 先序中序后序遍历方法. fbi树由于数量小,在递归每个区间时,暴力跑一遍区间里的数,看看是否有0和1.至于递归的方法,二 ...

  2. 二叉树的遍历 &amp&semi;【NOIP2001普及组】&amp&semi; 洛谷 P1030 求先序排列

    题目链接 https://www.luogu.org/problemnew/show/P1030 模板题 先讲一下二叉树的遍历 二叉树的遍历 分类 性质 求法 分为三类: 先序遍历(PreOrder) ...

  3. P1030 求先序排列 &sol;&sol;&sol; 二叉树的遍历

    题目大意: 给一棵树的中序排列 后序排列,求这棵树的先序排列 https://www.luogu.org/problemnew/show/P1030 二叉树的四种遍历解说 几种遍历的递归实现 后序排列 ...

  4. 洛谷 P1030 求先序排列 Label&colon;None

    题目描述 给出一棵二叉树的中序与后序排列.求出它的先序排列.(约定树结点用不同的大写字母表示,长度<=8). 输入输出格式 输入格式: 2行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序 ...

  5. 洛谷P1030求先序排列

    题目描述 给出一棵二叉树的中序与后序排列.求出它的先序排列.(约定树结点用不同的大写字母表示,长度≤8. 输入输出格式 输入格式: 2行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序排列. 输 ...

  6. P1030 求先序排列

    题目描述 给出一棵二叉树的中序与后序排列.求出它的先序排列.(约定树结点用不同的大写字母表示,长度<=8). 输入输出格式 输入格式: 2行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序 ...

  7. 洛谷 P1030 求先序排列

    题目描述 给出一棵二叉树的中序与后序排列.求出它的先序排列.(约定树结点用不同的大写字母表示,长度<=8). 输入输出格式 输入格式: 2行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序 ...

  8. 洛谷——P1030 求先序排列

    https://www.luogu.org/problem/show?pid=1030#sub 题目描述 给出一棵二叉树的中序与后序排列.求出它的先序排列.(约定树结点用不同的大写字母表示,长度&lt ...

  9. P1030 求先序排列 (一个非常棒的写法)

    理论正确就是真正的正确,误... 就是找嘛,找到每一个对应字符,然后对应的左右子树的区间,然后就可以了. #include <bits/stdc++.h> using namespace ...

随机推荐

  1. js中substr&comma;substring&comma;indexOf&comma;lastIndexOf的用法小结

    第一组:str.substr(start,length) 和 str.substring(start,end) 定义: str.substr(start,length) substr(start,le ...

  2. DOCTYPE 中xhtml 1&period;0和 html 4&period;01区别分析

    前者相对于后者有以下特性: 1.所有的标记都都要闭合 所有的标记都要闭合,如果是单独不成对的标签,在标签最后加一个"/"来关闭它.例如: <h6>close tag & ...

  3. Objective-C 学习笔记(Day 1)

    -------------------------------------------- Hello World //引入头文件 //c中的引入头文件的方式 //#include <stdio. ...

  4. Linux记录-sftp上传大文件

    1.Alt +P 进入sftp会话 2.pwd显示linux目录 lpwd显示windows目录 3.lcd切换windows目录 cd切换linux目录 4.put上传 5.get下载 6.help ...

  5. ServiceHub&period;DataWarehouseHost&period;exe内存泄漏问题的处理

    Visual Studio 2017的15.2版本在debug应用程序时,ServiceHub.DataWarehouseHost.exe会出现严重的内存泄漏的问题,一个小时左右,内存耗了将近8GB. ...

  6. 3&period; 原子变量-CAS算法

    1. 是什么 ? 2. CAS算法模拟 package com.gf.demo03; public class TestCompareAndSwap { public static void main ...

  7. web窗体之四则运算

    1,计算方法: namespace ASP.NET { public class JiSuan { public int S; public int Result { get { return S; ...

  8. 1003 我要通过!&vert; PAT &lpar;Basic Level&rpar; Practice

    1003 我要通过! (20 分) "答案正确"是自动判题系统给出的最令人欢喜的回复.本题属于 PAT 的"答案正确"大派送 -- 只要读入的字符串满足下列条件 ...

  9. dp之混合背包poj1742(推荐)

    题意:给你价值为a1,a2.....的货币,每种有c1,c2.......个,求这些货币所能组成的价值小于等于m有多少个..... 思路:很像一道多重背包题?那我一开始的确是用多重背包的思路编写的.. ...

  10. sublime3配置java开发环境

    链接:http://www.jianshu.com/p/48a524a4f63c 或者:http://www.jianshu.com/p/9d167c4c4feb 侵权删!