Editorial for Duyệt cây nhị phân


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <cstdio>
using namespace std;

int n,preOrder[50100],inOrder[50100],pos[50100];

void postOrder(int l,int r,int ll,int rr)
{
    int x=pos[preOrder[l]];
    if (x>ll) postOrder(l+1,l+x-ll,ll,x-1);
    if (x<rr) postOrder(r-rr+x+1,r,x+1,rr);
    printf("%d ",preOrder[l]);
}

int main()
{
    int x;
    scanf("%d",&n);
    for (int i=0;i<n;i++) scanf("%d",&preOrder[i]);
    for (int i=0;i<n;i++) scanf("%d",&x), pos[x]=i;
    postOrder(0,n-1,0,n-1);
}

Code mẫu của happyboy99x

#include<cstdio>

const int N = 50000 + 5;
int n, pre[N], in[N], pIn[N];

void construct(int a, int b, int n) {
    if(n == 0) return;
    int pos = pIn[pre[a]];
    construct(a + 1, b, pos - b);
    construct(a + 1 + pos - b, pos + 1, b + n - pos - 1);
    printf("%d ", pre[a]);
}

void enter() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", &pre[i]);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &in[i]);
        pIn[in[i]] = i;
    }
}

int main() {
    enter();
    construct(0, 0, n);
    return 0;
}

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (REACHEOF) return 0;\
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);
const int MN = 50111;

int a[MN], b[MN], inb[MN];

void solve(int la, int ra, int lb, int rb) {
    int u = a[la];
    int posu = inb[u];
    int size_l = posu - lb;
    int size_r = (rb - lb) - size_l;

    if (size_l) solve(la+1, la+size_l, lb, posu-1);
    if (size_r) solve(la+size_l+1, ra, posu+1, rb);
    printf("%d ", u);
}

int main() {
    int n; scanf("%d", &n);
    FOR(i,1,n) scanf("%d", &a[i]);
    FOR(i,1,n) {
        scanf("%d", &b[i]);
        inb[b[i]] = i;
    }
    solve(1,n,1,n);
    puts("");
    return 0;
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define ep 0.00001
#define maxn 100111
#define oo 1111111111
#define modunlo 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int n,a[55555],vitri[55555],x;
VI V;

void xuly(int u,int v,int p,int q){
     if(u>v) return ;
     if(u==v){
          V.push_back(a[u]);
          return;
     }
     V.push_back(a[u]);
     int t = vitri[a[u]];
     xuly(u+t-p+1,v,t+1,q);
     xuly(u+1,u+t-p,p,t-1);
}

int main(){

    // freopen("BINTREE.in","r",stdin);
    // freopen("BINTREE.out","w",stdout);
     scanf("%d",&n);
     for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
     for(int i = 1;i<=n;i++) {
           scanf("%d",&x);
           vitri[x] = i;
     }
     xuly(1,n,1,n);
     for(int i = n-1;i>=0;i--) printf("%d ",V[i]); 
}

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   50505
struct nod
{
    int parent,left,right;
};
nod bt[MAX];
int pr[MAX];
int in[MAX];
int pr1[MAX];
int in1[MAX];
int n,v;
int vs[MAX];
void build(int num,int fpr,int fin)
{
    if (num<2) return;
    if (in1[pr[fpr]]==fin)
        {
            bt[pr[fpr]].right=pr[fpr+1];
            bt[pr[fpr+1]].parent=pr[fpr];
            build(num-1,fpr+1,fin+1);
            return;
        }
    if (in1[pr[fpr]]==fin+num-1)
        {
            bt[pr[fpr]].left=pr[fpr+1];
            bt[pr[fpr+1]].parent=pr[fpr];
            build(num-1,fpr+1,fin);
            return;
        }
    bt[pr[fpr]].left=pr[fpr+1];
    bt[pr[fpr+1]].parent=pr[fpr];
    bt[pr[fpr]].right=pr[fpr+in1[pr[fpr]]-fin+1];
    bt[pr[fpr+in1[pr[fpr]]-fin+1]].parent=pr[fpr];
    build(in1[pr[fpr]]-fin,fpr+1,fin);
    build(num-in1[pr[fpr]]+fin-1,fpr+in1[pr[fpr]]-fin+1,in1[pr[fpr]]+1);
}
void visit(int x)
{
    if (bt[x].left>0) visit(bt[x].left);
    if (bt[x].right>0) visit(bt[x].right);
    v=v+1;
    vs[v]=x;
}
void process(void)
{
    int i;
    scanf("%d",&n);
    for (i=1;i<=n;i=i+1)
        {
            scanf("%d",&pr[i]);
            pr1[pr[i]]=i;
        }
    for (i=1;i<=n;i=i+1)
        {
            scanf("%d",&in[i]);
            in1[in[i]]=i;
        }
    for (i=1;i<=n;i=i+1)
        {
            bt[i].parent=-1;
            bt[i].left=-1;
            bt[i].right=-1;
        }
    v=0;
    build(n,1,1);   
    visit(pr[1]);
    for (i=1;i<n;i=i+1)
        printf("%d ",vs[i]);
    printf("%d",vs[n]);
}
int main(void)
{   
    process();  
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.