https://www.patest.cn/contests/pat-t-practise/1006
code 来自于http://blog.csdn.net/jtjy568805874/article/details/50759512
dfs 在中序遍历序列中穷举 root 的位置，因为root可能会被替换，所以使用数组存储树。
#include <cstdio> #include <queue> #include <algorithm> using namespace std; const int maxn = 1e2 + 10; int n, ch[maxn][2], root, a[maxn], b[maxn], c[maxn], f[maxn], v[maxn]; int flag; int get() { char s[20]; scanf("%s",s); if (s[0] == '-') return 0; int res = 0; for (int i = 0; s[i]; i++) res = res * 10 + s[i] - '0'; return res; } //以中序遍历数组的idx[1~n]为树的root的指针，dfs测试root. bool dfs(int &x, int al, int ar, int bl, int br, int cl, int cr) { if (al > ar) { x = 0; return true; } for (int i = al; i <=ar ; i++) { /*下面三行是测试root的值的*/ if (a[i] && b[bl] && a[i] != b[bl]) continue; if (a[i] && c[cr] && a[i] != c[cr]) continue; if (b[bl] && c[cr] && b[bl] != c[cr]) continue; v[i] = max(a[i], max(b[bl], c[cr])); x = i; if (!dfs(ch[x][0], al, i - 1, bl + 1, bl + i - al, cl, cl + i - al - 1)) continue; if (!dfs(ch[x][1], i + 1, ar, bl + 1 + i - al, br, cl + i - al, cr - 1)) continue; return true; } return false; } void dfs(int x,int y) { if (!x) return; if (y == 2) { printf("%s%d", flag ? " ": "", v[x]); flag = 1; } dfs(ch[x][0], y); if (y == 1) { printf("%s%d", flag ? " " :"", v[x]); flag = 1; } dfs(ch[x][1], y); if (y == 3) { printf("%s%d", flag ? " " : "",v[x]); flag = 1; } } void bfs(int x) { queue<int> q; q.push(x); while (!q.empty()) { int p = q.front(); q.pop(); printf("%s%d", flag ? " " : "", v[p]); flag = 1; if (ch[p][0]) q.push(ch[p][0]); if (ch[p][1]) q.push(ch[p][1]); } } int main() { scanf("%d", &n); int cnt = 0;//missing digit int res; // the missing one for (int i = 1; i <= n; i++) { a[i] = get(); f[a[i]]++; } for (int i = 1; i <= n; i++) { b[i] = get(); f[b[i]]++; } for (int i = 1; i <= n; i++) { c[i] = get(); f[c[i]]++; } for (int i = 1; i <= n; i++) {if (!f[i]) cnt++; res = i; } if (cnt > 1 || !dfs(root, 1, n, 1, n, 1, n)) printf("Impossible\n"); else { for (int i = 1; i <= n; i++) if (!v[i]) v[i] = res; flag = 0; dfs(root, 1); putchar(10); flag = 0; dfs(root, 2); putchar(10); flag = 0; dfs(root, 3); putchar(10); flag = 0; bfs(root); putchar(10); } return 0; }