PAT (Top Level) Practice1006 Tree Traversals - Hard Version （35 分）

题目链接：https://pintia.cn/problem-sets/994805148990160896/problems/994805154321121280

dfs加剪枝，很麻烦，具体看代码。

算法：dfs

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <queue>
using namespace std;
 
const int maxn = 110;
int inorder[maxn], preorder[maxn], postorder[maxn], t[maxn], tree[maxn][2], f[maxn], root;
int rein[maxn], repre[maxn], repost[maxn];
bool flag;
 
bool dfs(int &index, int inl, int inr, int prel, int prer, int postl, int postr);
void dfs(int root, int p);
void bfs(void);
int get(void);
 
int main(void) {
	int i, n, cnt = 0, residue;
	scanf(\"%d\", &n);
	for (i = 1; i <= n; i++) inorder[i] = get(), f[inorder[i]]++, rein[inorder[i]] = i;
	for (i = 1; i <= n; i++) preorder[i] = get(), f[preorder[i]]++, repre[preorder[i]] = i;
	for (i = 1; i <= n; i++) postorder[i] = get(), f[postorder[i]]++, repost[postorder[i]] = i;
	for (i = 1; i <= n; i++) if (!f[i]) cnt++, residue = i;
	if(cnt > 1 || !dfs(root, 1, n, 1, n, 1, n)) puts(\"Impossible\");
	else {
		for (i = 1; i <= n; i++) if (!t[i]) t[i] = residue;
		flag = 0, dfs(root, 2), putchar(\'\\n\');
		flag = 0, dfs(root, 1), putchar(\'\\n\');
		flag = 0, dfs(root, 3), putchar(\'\\n\');
		flag = 0, bfs();
	}
	return 0;
}
 
bool dfs(int &index, int inl, int inr, int prel, int prer, int postl, int postr) {
	int i, tmp;
	if (inl > inr) {
		index = 0; 
		return true;
	}
	for (i = inl; i <= inr; i++) {
		if (inorder[i] && preorder[prel] && inorder[i] != preorder[prel]) continue;
		if (inorder[i] && postorder[postr] && inorder[i] != postorder[postr]) continue;
		if (preorder[prel] && postorder[postr] && preorder[prel] != postorder[postr]) return false;
		tmp = max(inorder[i], max(preorder[prel], postorder[postr]));
		if (rein[tmp] && rein[tmp] != i) continue;
		if (repre[tmp] && repre[tmp] != prel) continue;
		if (repost[tmp] && repost[tmp] != postr) continue;
		if (!dfs(tree[i][0], inl, i - 1, prel + 1, prel + i - inl, postl, postl + i - inl - 1)) continue;
		if (!dfs(tree[i][1], i + 1, inr, prel + i - inl + 1, prer, postl + i - inl, postr - 1)) continue;
		index = i;
		t[index] = tmp;
		return true;
	}
	return false;
}
void dfs(int root, int p) {
	if (!root) return;
	if (p == 1) printf(\"%s%d\", flag ? \" \" : \"\", t[root]), flag = true;
	dfs(tree[root][0], p);
	if (p == 2) printf(\"%s%d\", flag ? \" \" : \"\", t[root]), flag = true;
	dfs(tree[root][1], p);
	if (p == 3) printf(\"%s%d\", flag ? \" \" : \"\", t[root]), flag = true;
	return;
}
void bfs(void) {
	queue<int> q;
	int tmp;
	q.push(root);
	printf(\"%d\", t[root]);
	while (!q.empty()) {
		tmp = q.front();
		q.pop();
		if (tree[tmp][0]) q.push(tree[tmp][0]), printf(\" %d\", t[tree[tmp][0]]);
		if (tree[tmp][1]) q.push(tree[tmp][1]), printf(\" %d\", t[tree[tmp][1]]);
	}
	return;
}
int get(void) {
	int tmp, i;
	char str[10];
	scanf(\"%s\", str);
	if (str[0] == \'-\') {
		return 0;
	}
	else {
		tmp = 0;
		for (i = 0; str[i]; i++) {
			tmp = tmp * 10 + str[i] - \'0\';
		}
		return tmp;
	}
}