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.
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