这是一道面试题,可以说是数据结构中的基础题了,由先序遍历以及中序遍历生成一棵树,然后输出后序遍历。
一个递归函数传递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; }