注释版：
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); using namespace std; typedef long long ll; const int maxn=50; int mid[maxn],po[maxn],pr[maxn]; int first; struct node { int l,r; }T[maxn]; // 中序+先序=>二叉树 int mid_pr_build(int la,int ra,int lb,int rb) // la,ra：表示中序遍历 lb,rb：表示先序遍历 { // 这里不能等于，因为假设：len==1，则la==ra，直接返回，但是实际上是有一个 rt 的，却没被建立 if(la>ra) return 0; int rt=pr[lb]; // 因为先序遍历第一个是根节点 int p1=la,p2; while(mid[p1]!=rt) p1++; // 在中序遍历中找到根节点 p2=p1-la; T[rt].l=mid_pr_build(la,p1-1,lb+1,lb+p2); // 左子树（锁定左子树范围的下标） T[rt].r=mid_pr_build(p1+1,ra,lb+p2+1,rb); // 右子树（锁定右子树范围的下标） return rt; } // 中序+后序=>二叉树 int mid_po_build(int la,int ra,int lb,int rb) // la,ra：表示中序遍历 lb,rb：表示后序遍历 { if(la>ra) return 0; int rt=po[rb]; // 因为后序遍历最后一个是根节点 int p1=la,p2; while(mid[p1]!=rt) p1++; // 在中序遍历中找到根节点 p2=p1-la; T[rt].l=mid_po_build(la,p1-1,lb,lb+p2-1); // 左子树（锁定左子树范围的下标） T[rt].r=mid_po_build(p1+1,ra,lb+p2,rb-1); // 右子树（锁定右子树范围的下标） return rt; } // 求树高 int getHeight(int rt) { if(rt==0) return 0; return 1+max(getHeight(T[rt].l),getHeight(T[rt].r)); } // 层序遍历 void bfs(int rt) { queue<int> q; vector<int> v; q.push(rt); while(!q.empty()) { int w=q.front(); q.pop(); v.push_back(w); if(T[w].l!=0) q.push(T[w].l); if(T[w].r!=0) q.push(T[w].r); } int len=v.size(); for(int i=0;i<len;i++) printf("%d%c",v[i],i==len-1?'\n':' '); // 推荐这种写法，简洁 } // 先序遍历 void preT(int rt) { if(rt==0) return; printf(first?first=0,"%d":" %d",rt); preT(T[rt].l); preT(T[rt].r); } // 中序遍历 void midT(int rt) { if(rt==0) return; midT(T[rt].l); printf(first?first=0,"%d":" %d",rt); midT(T[rt].r); } // 中倒序遍历 void reMidT(int rt) { if(rt==0) return; midT(T[rt].r); printf(first?first=0,"%d":" %d",rt); midT(T[rt].l); } // 后序遍历 void postT(int rt) { if(rt==0) return; postT(T[rt].l); postT(T[rt].r); printf(first?first=0,"%d":" %d",rt); } int main() { int n; while(~scanf("%d",&n)) { first=1; for(int i=0;i<n;i++) scanf("%d",&po[i]); // 后序结点 // for(int i=0;i<n;i++) scanf("%d",&pr[i]); // 先序结点 for(int i=0;i<n;i++) scanf("%d",&mid[i]); // 中序结点 int rt=mid_po_build(0,n-1,0,n-1); // 中+后，返回根节点 // int rt=mid_pr_build(0,n-1,0,n-1); // 中+先，返回根节点 bfs(rt); // 层序遍历 // preT(rt); // 先序遍历 // puts(""); // postT(rt); // 后序遍历 // puts(""); // midT(rt); // 中序遍历 // puts(""); } return 0; }
简化版（Val As Index，若数据不在1~N内，则可能越界）：
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); using namespace std; typedef long long ll; const int maxn=50; int mid[maxn],po[maxn],pr[maxn]; int first; struct node { int l,r; }T[maxn]; int mid_pr_build(int la,int ra,int lb,int rb) { if(la>ra) return 0; int rt=pr[lb]; int p1=la,p2; while(mid[p1]!=rt) p1++; p2=p1-la; T[rt].l=mid_pr_build(la,p1-1,lb+1,lb+p2); T[rt].r=mid_pr_build(p1+1,ra,lb+p2+1,rb); return rt; } int mid_po_build(int la,int ra,int lb,int rb) { if(la>ra) return 0; int rt=po[rb]; int p1=la,p2; while(mid[p1]!=rt) p1++; p2=p1-la; T[rt].l=mid_po_build(la,p1-1,lb,lb+p2-1); T[rt].r=mid_po_build(p1+1,ra,lb+p2,rb-1); return rt; } int getHeight(int rt) { if(rt==0) return 0; return 1+max(getHeight(T[rt].l),getHeight(T[rt].r)); } void bfs(int rt) { queue<int> q; vector<int> v; q.push(rt); while(!q.empty()) { int w=q.front(); q.pop(); v.push_back(w); if(T[w].l!=0) q.push(T[w].l); if(T[w].r!=0) q.push(T[w].r); } int len=v.size(); for(int i=0;i<len;i++) printf("%d%c",v[i],i==len-1?'\n':' '); } void preT(int rt) { if(rt==0) return; printf(first?first=0,"%d":" %d",rt); preT(T[rt].l); preT(T[rt].r); } void midT(int rt) { if(rt==0) return; midT(T[rt].l); printf(first?first=0,"%d":" %d",rt); midT(T[rt].r); } void reMidT(int rt) { if(rt==0) return; midT(T[rt].r); printf(first?first=0,"%d":" %d",rt); midT(T[rt].l); } void postT(int rt) { if(rt==0) return; postT(T[rt].l); postT(T[rt].r); printf(first?first=0,"%d":" %d",rt); } int main() { int n; while(~scanf("%d",&n)) { first=1; for(int i=0;i<n;i++) scanf("%d",&po[i]); // for(int i=0;i<n;i++) scanf("%d",&pr[i]); for(int i=0;i<n;i++) scanf("%d",&mid[i]); int rt=mid_po_build(0,n-1,0,n-1); // int rt=mid_pr_build(0,n-1,0,n-1); bfs(rt); // preT(rt); // postT(rt); // midT(rt); } return 0; }
简化版（Val Not As Index，可以存任意的 Val）：
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define ssclr(ss) ss.clear(), ss.str("") #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int maxn=5e4+1000; int f; int pre[maxn], in[maxn]; struct node { int l,r,d; }T[maxn]; int create(int l1,int r1,int l2,int r2) // in pre { if(l2>r2) return -1; int rt=l2; int p1=l1,p2; while(in[p1]!=pre[rt]) p1++; p2=p1-l1; T[rt].d=pre[rt]; T[rt].l=create(l1,p1-1,l2+1,l2+p2); T[rt].r=create(p1+1,r1,l2+p2+1,r2); return rt; } void postT(int rt) { if(rt==-1 || !f) return; postT(T[rt].l); postT(T[rt].r); if(f) f=0, printf("%d\n",T[rt].d); } int main() { int n; 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]); int rt=create(0,n-1,0,n-1); f=1, postT(rt); return 0; }
