Hướng dẫn giải của Duyệt cây nhị phân
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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(); }
Bình luận