说明：这是重庆交通大学第10届大学生程序设计大赛的题目，应该只有本校生能提交。

题目

Lucy最近正在学习数据结构中的二叉树，为了更好学习二叉树的几种遍历，Lucy常常自己随机写一些二叉树。比如说下面这样的一棵二叉树。

截屏2024-03-01 21.33.39

但是计算机是不能输入这样的图形的，只能用一组序列来保存二叉树：前序遍历序列、后序遍历序列、或中序遍历序列。前序序列，节点访问顺序为：根，左子树，右子树。中序序列，节点访问顺序为：左子树，根，右子树。后序序列，节点访问顺序为：根，左子树，右子树。

如下图，前序遍历序列为ABDEGHJCFI，中序遍历序列为DBGEHJACIF，而后序遍历序列为DGJHEBIFCA。

在本题中，输入一棵二叉树的前序和后序遍历序列，再输入n个长度相等的序列，判断这些序列是否可能为该二叉树的中序遍历序列。

输入描述：

输入数据第一行为一棵二叉树的前序遍历序列和后序遍历序列，用空格隔开，每个序列由26个大写字母组成且每个节点的字母不重复，所以两个遍历序列的长度都不超过26。第二行为正整数n，$n \le 10$，接下来有n行，每行是一个由大写字母构成的序列，这n个序列互不相同，保证长度和第一行中的两个序列长度相等，且保证出现的字母和第一行中的两个序列出现的字母一样。

输出描述：

如果n个待判定的序列中存在对应二叉树的中序遍历序列，输出它们的序号，序号从1开始计起，按从小到大的顺序输出，每个序号占一行。如果n个待判定的序列都不是中序遍历序列，输出none。

注意，由前序遍历序列和后序遍历序列不能确定一棵二叉树，所以n个序列中可能有多个是中序遍历序列。

样例输入1：

ABDEGHJCFI DGJHEBIFCA

3

ADBGEHJCIF

DGBEHJACIF

DBGEHJACIF

样例输出1:

3

样例输入2:

ABDEGHJCFI DGJHEBIFCA

3

ADBGEHJCIF

DGBEHJACIF

DBGEHJAICF

样例输出2:

none

实现思路

「背景性质」：

二叉树有一个性质是：可以由前序遍历和中序遍历重新构建二叉树。或者由后序遍历和中序遍历重新构建二叉树。

简单说明一下这个性质：（说明前序+中序。后序+中序同理）

前序遍历：根节点，左子树，右子树

中序遍历：左子树，根节点，右子树

这里我们知道，树的根节点一定是前序遍历中的第一个元素。那么我们把这个元素放到中序遍历中，这个元素左边的元素就是这颗树的根节点的左子树，同理，右边的元素就是右子树。

接着，去掉第一个元素的前序遍历的第一个元素一定是子树（可能没有左子树）的根节点。然后再从中序遍历得到的左子树序列和右子树序列中寻找值。

如此其实可以得出是一个递归的过程。

「本题思路」：

这道题和 中序和后序重构二叉树 的题型是差不多的，只是这道题稍微绕一点。

后序遍历和中序遍历也能构建一颗二叉树，我这里选用前序+中序（读者可以尝试自己用后序+中序实现一下）。

读入题目的前序遍历序列和后序遍历序列后。再读入中序遍历序列，使用这个中序遍历序列号前序遍历序列结合重构一颗二叉树。

再对这颗重构好的二叉树进行后序遍历，比较是否和题目中的后序遍历序列相同。相同则加一。

具体实现看代码（几乎每行都有注释）。

注意：题目中的数据不保证一定可以构成一颗树。代码中要判断。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstring>
#include <map>

using namespace std;

int n, m, ans; // n为树的节点个数，m为样例数量，ans判断有无结果
string pre, in, post, res; // 前序遍历字符串，中序遍历字符串，后序遍历字符串
map<char, pair<char, char> > g;	// 存重构后的二叉树，第一个char为当前节点值
								//pair<char, char>为其{left, right}

void init() {
	g.clear(); // 把重构二叉树置为空
	res = ""; // 重构二叉树的后序遍历结果置为空
}

// 重构二叉树
char find_root (int pr, int il, int ir) {
	if (il > ir) return '0'; // 避免评判数据中根本不可能构成树的情况
	char root = pre[pr]; // 当前子树的根
    if (il == ir) { // 刚好一个节点，为叶子节点，其左右节点均为空
    	g[root] = {'0', '0'};
    	return root;
    }
    int pos = in.find(root);
    if (pos < il) return '0'; // 避免评判中根本不可能构成树的情况
    
	char left = find_root(pr+1, il, pos-1); // 继续遍历左子树
	char right = find_root(pr+pos-il+1, pos+1, ir); // 继续遍历右子树
	g[root] = {left, right};
	
	return root;
}

// 后序遍历二叉树
void dfs(char u) { // 当前节点
    if (u == '0') return; // 为空不遍历
	if (g[u].first != '0') // 左节点不为空，则遍历左节点
		dfs(g[u].first); // 左节点
	if (g[u].second != '0') // 右节点不为空，则遍历右节点
		dfs(g[u].second); // 右节点
	
	res = res + u;
}

bool judge() {
	char root = find_root(0, 0, n-1); // 重构二叉树
	dfs(root); // 后序遍历二叉树
    // 比较重新构建的二叉树的后序遍历与题目的后序遍历是否相同
	if (res == post) return true;
	return false;
}

int main() {
	cin >> pre >> post;
	n = pre.size();
	cin >> m;
	for (int i = 1; i <= m; ++i) {
		init();

		cin >> in;

		if (judge()) { // 判断是否是正确的解
			cout << i << endl;
			ans ++;
		}
	}
	if (ans == 0) puts("none");
}

最终提交结果：

截屏2024-03-01 21.33.39