P1030 求先序排列 P1305 新二叉树

　　

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度\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 新二叉树的相关教程结束。