這是一道面試題,可以說是數據結構中的基礎題了,由先序遍歷以及中序遍歷生成一棵樹,然后輸出后序遍歷。
一個遞歸函數傳遞5個參數,頂點編號,先序左右區間,中序左右區間,每次進行區間長度判定,當只有一個元素就進行元素判定,遞歸構樹。
代碼如下:
#include <cstdlib> #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #define MAXN 1005 using namespace std;int N, p[MAXN], m[MAXN], idx;struct Node {int l, r, val; }e[MAXN];int init() {++idx;e[idx].l = e[idx].r = 0;return idx; }bool build(int rt, int l, int r, int ll, int rr) { // l, r 表示先序的區間,ll, rr表示中序的區間 int pos = -1;e[rt].val = p[l]; // 先序確定根節點if (r - l != rr - ll) return false;if (l == r) {if (p[l] == m[ll]) return true;else return false;}for (int i = ll; i <= rr; ++i) { // 中序尋根 if (m[i] == p[l]) {pos = i;break;}}if (pos == -1) return false;if (pos == ll) { // 沒有左孩子e[rt].r = init();return build(e[rt].r, l+1, r, ll+1, rr);}else if (pos == rr) { // 沒有右孩子 e[rt].l = init();return build(e[rt].l, l+1, r, ll, rr-1);}else {int a, b;e[rt].l = init();a = build(e[rt].l, l+1, l+(pos-ll), ll, pos-1);e[rt].r = init();b = build(e[rt].r, l+(pos-ll)+1, r, pos+1, rr);return a && b;} }void print(int p) {if (e[p].l) {print(e[p].l); }if (e[p].r) {print(e[p].r); }printf("%d ", e[p].val); }int main() {int rt;while (scanf("%d", &N) == 1) {idx = -1;rt = init();for (int i = 1; i <= N; ++i) {scanf("%d", &p[i]);}for (int i = 1; i <= N; ++i) {scanf("%d", &m[i]);}if (build(rt, 1, N, 1, N)) {print(rt);puts("");}else puts("No");}return 0; }