思路1： 先用后序序列（postorder）和中序序列（inorder）建立起二叉树，再用BFS（一个queue）将层序遍历序列输出
code1:
#include <queue> #include <cstring> #include <algorithm> #include <stdio.h> using namespace std; const int maxn = 100; int n, post[maxn], in[maxn]; struct node{ int data; node* lc; node* rc; }; node* create(int postL, int postR, int inL, int inR){ if(postL >= postR) return NULL; node* root = new node; root->data = post[postR-1]; root->lc = NULL; root->rc = NULL; int i; for(i = inL; i < inR; ++i){ if(in[i] == post[postR-1]) break; } int num = i - inL; //Q:为什么必须用num？直接i出错 root->lc = create(postL, postL+num, inL, i); root->rc = create(postL+num, postR-1, i+1, inR); return root; } int num = 0; //已经输出节点个数 void BFS(node* root){ queue<node*> q; q.push(root); while(!q.empty()){ node* now = new node; now = q.front(); q.pop(); printf(now->data); num++; if(num < n) printf(" "); if(now->lc != NULL) q.push(now->lc); if(now->rc != NULL) q.push(now->rc); } } int main(){ scanf("%d", &n); for(int i = 0; i < n; ++i){ scanf("%d", post+i); } for(int i = 0; i < n; ++i){ scanf("%d", in+i); } node* root = create(0, n, 0, n); BFS(root); return 0; } 上面是按[L, R)来建立二叉树，如果中序后序区间改为[L, R]的话，改动如下 node* create(int postL, int postR, int inL, int inR){ if(postL > postR) return NULL; ... for(i = inL; i <= inR; ++i) ... root->lc = create(postL, postL+num-1, inL, i+1); root->rc = create(postL+num, postR-1, i+1, inR); return root; } int main(){ .... node* root = create(0, n-1, 0, n-1); ... }思路 2：静态树存储，建树+BFS
T2 code:
#include <bits/stdc++.h> using namespace std; const int maxn = 110; int post[maxn], in[maxn], idex = 0; struct Node{ int data, lc, rc; Node(){ lc = rc = -1; } }node[maxn]; int NewNode(int x){ node[idex].data = x; node[idex].lc = -1; node[idex].rc = -1; return idex++; } int Create(int postL, int postR, int inL, int inR){ if(postL > postR){ return -1; } int r = NewNode(post[postR]); // cout << post[postR] <<endl; int id = inL; while(id <= inR && in[id] != post[postR]) id++; int numL = id - inL; node[r].lc = Create(postL, postL + numL -1, inL, id - 1); node[r].rc = Create(postL + numL, postR - 1, id + 1, inR); return r; } int n, cnt = 0; void BFS(int r){ queue<int> q; q.push(r); while(!q.empty()){ int now = q.front(); printf("%d", node[now].data); if(++cnt < n) printf(" "); q.pop(); if(node[now].lc != -1) q.push(node[now].lc); if(node[now].rc != -1) q.push(node[now].rc); } } int main(){ scanf("%d", &n); for(int i = 0; i < n; ++i){ scanf("%d", &post[i]); } for(int i = 0; i < n; ++i){ scanf("%d", &in[i]); } int r = Create(0, n-1, 0, n-1); BFS(r); return 0; }思路3： 不建树，Create()中加一个layer参数，将树按layer输入二维数组中，再按层遍历二维数组
T2 code:
#include <bits/stdc++.h> using namespace std; const int maxn = 110; int post[maxn], in[maxn]; int n, max_layer = 0; vector<int> n_layer[maxn]; void Create(int layer, int postL, int postR, int inL, int inR){ if(postL > postR){ max_layer = max(max_layer, layer); return; } int r = post[postR]; n_layer[layer].push_back(r); int id = inL; while(id <= inR && in[id] != post[postR]) id++; int numL = id - inL; Create(layer + 1, postL, postL + numL -1, inL, id - 1); Create(layer + 1, postL + numL, postR - 1, id + 1, inR); } int main(){ scanf("%d", &n); for(int i = 0; i < n; ++i){ scanf("%d", &post[i]); } for(int i = 0; i < n; ++i){ scanf("%d", &in[i]); } Create(0, 0, n-1, 0, n-1); int cnt = 0; for(int i = 0; i < max_layer; ++i){ for(int j = 0; j < n_layer[i].size(); ++j){ printf("%d", n_layer[i][j]); if(++cnt < n) printf(" "); } } // BFS(root); return 0; } T3 code： 不建树，数组存储法（改成set或priority_queue实现） 直接输出 set版本： #include <bits/stdc++.h> using namespace std; const int maxn = 50; vector<int> post, in; struct Node { int data, id; bool operator < (const Node & tmp) const { return id < tmp.id; } }; set<Node> ans; void Create(int postL, int postR, int inL, int inR, int id) { if(postL >= postR) return; int r = post[postR-1], tid = inL; ans.insert(Node{r, id}); while(tid < inR && in[tid] != r) tid++; int numL = tid - inL; Create(postL, postL+numL, inL, tid, 2*id); Create(postL+numL, postR-1, tid+1, inR, 2*id+1); } int main() { int n; scanf("%d", &n); post.resize(n); in.resize(n); for(int i = 0; i < n; ++i) { scanf("%d", &post[i]); } for(int i = 0; i < n; ++i) { scanf("%d", &in[i]); } Create(0, n, 0, n, 1); for(auto it = ans.begin(); it != ans.end(); ++it) { if(it == ans.begin()) printf("%d", (*it).data); else printf(" %d", (*it).data); } return 0; }priority_queue版本：
#include <bits/stdc++.h> using namespace std; const int maxn = 50; vector<int> post, in; struct Node { int data, id; bool operator < (const Node & tmp) const { return id > tmp.id; } }; priority_queue<Node> ans; void Create(int postL, int postR, int inL, int inR, int id) { if(postL >= postR) return; int r = post[postR-1], tid = inL; ans.push(Node{r, id}); while(tid < inR && in[tid] != r) tid++; int numL = tid - inL; Create(postL, postL+numL, inL, tid, 2*id); Create(postL+numL, postR-1, tid+1, inR, 2*id+1); } int main() { int n; scanf("%d", &n); post.resize(n); in.resize(n); for(int i = 0; i < n; ++i) { scanf("%d", &post[i]); } for(int i = 0; i < n; ++i) { scanf("%d", &in[i]); } Create(0, n, 0, n, 1); int cnt = 0; while(!ans.empty()) { printf("%d", ans.top()); ans.pop(); if(++cnt < n) printf(" "); } return 0; } T5: #include <bits/stdc++.h> using namespace std; vector<int> post, in; unordered_map<int, int> pos_in; typedef pair<int, int> pr; // <id, val> priority_queue<pr, vector<pr>, greater<pr> > pq; void Create(int postL, int postR, int inL, int inR, int id){ //在[postL, postR)建树 if(postL >= postR) return; int r = post[postR-1], tid = pos_in[r], numL = tid - inL; pq.push(make_pair(id, r)); Create(postL, postL+numL, inL, tid, 2*id); Create(postL+numL, postR-1, tid+1, inR, 2*id+1); } int main(){ int n; scanf("%d", &n); post.resize(n); in.resize(n); for(int i = 0; i < n; ++i) scanf("%d", &post[i]); for(int i = 0; i < n; ++i){ scanf("%d", &in[i]); pos_in[in[i]] = i; } Create(0, n, 0, n, 1); while(!pq.empty()){ printf("%d", pq.top().second); pq.pop(); if(!pq.empty()) printf(" "); } return 0; }