1119 Pre- and Post-order Traversals (30分)

题目大意：给出一棵树的结点个数n，以及它的前序遍历和后序遍历，输出它的中序遍历，如果中序遍历不唯一就输出No，且输出其中一个中序即可，如果中序遍历唯一就输出Yes，并输出它的中序

主要是如何判断结果是否唯一，已知二叉树的前序和后序是无法唯一确定一颗二叉树的，因为可能会存在多种情况。当只有一个孩子节点的时候，无法判断这个孩子节点是左孩子还是右孩子

先查看中序遍历是否唯一，先序遍历顺序为：根左右，后序遍历顺序为：左右根，那么如果一个节点只包含左子节点或者只包含右子节点，但是根据上面的顺序可以发现，他们的先序遍历和后续遍历是没有发生变化的，例如：

))

此图中节点1，节点3，只含有左子节点或者右子节点，但是他们的先序遍历和后续遍历都是相同的：

先序遍历：1 2 5 3 4

后序遍历：5 4 3 2 1

所以只要父亲节点只包含一个子节点，那么这个答案就是不唯一的

后序遍历和先序遍历得到中序遍历（例一为例）

先序遍历： 1 2 3 4 6 7 5 后序遍历： 2 6 7 4 5 3 1

在先序遍历中先取出开始的节点1，这个节点定为当前根节点，1后面一个节点2一定是节点1的一个子节点，然后在后序遍历中寻找节点2，于是便可知节点2（包括2）之前的位于节点1的左子树中，2（不包括2）后面的节点直至节点1，位于节点1的右子树

节点2 3 6 7 5位于节点1的右子树中，根据先序遍历可知3为这个子树的根节点，节点4为节点3的左或右子节点中的一个，后序遍历中找到节点4，可以知道节点6 7 4位于节点3的左子树中，节点5位于节点3的右子树中

依次类推，可以遍历完这棵树，于是便可得到中序遍历

如果上述中找到只包含一个子节点的父节点，没有发现另外一个节点，即当前遍历区间中只包含当前节点的一个子节点，说明这个树是不唯一的，我们默认情况下将其安排在左子节点中

#include <bits/stdc++.h>
using namespace std;
const int maxn = 30 + 10;

int pre[maxn], post[maxn];
vector<int> in;
bool flag;
void in_order(int preLeft, int preRight, int postLeft, int postRight) {
	if (preLeft == preRight) {
		in.push_back(pre[preLeft]);
		return;
	}
	if (pre[preLeft] == post[postRight]) {
		int i = preLeft + 1;
		while (i <= preRight && pre[i] != post[postRight - 1])
			i++;
		if (i - preLeft > 1) //父节点有两个子节点，结构唯一
			in_order(preLeft + 1, i - 1, postLeft, postLeft + (i - preLeft - 1) - 1); //左子树
		else if (i - preLeft == 1) //父节点有一个子节点，则可左可右，结构不唯一
			flag = false;
		in.push_back(pre[preLeft]);  //根节点
		in_order(i, preRight, postLeft + (i - preLeft - 1), postRight - 1);  //右子树
	}
}

int main(int argc, char const *argv[])
{
	int N, i;
	cin >> N;
	for (int i = 0; i < N; ++i)
		cin >> pre[i];
	for (int i = 0; i < N; ++i)
		cin >> post[i];
	flag = true;
	in_order(0, N - 1, 0, N - 1);
	if (flag)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	for (i = 0; i < N - 1; ++i)
		cout << in[i] << " ";
	cout << in[i] << endl;

	return 0;
}