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

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences, or preorder and inorder traversal sequences. However, if only the postorder and preorder traversal sequences are given, the corresponding tree may no longer be unique.

Now given a pair of postorder and preorder traversal sequences, you are supposed to output the corresponding inorder traversal sequence of the tree. If the tree is not unique, simply output any one of them.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 30), the total number of nodes in the binary tree. The second line gives the preorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, first printf in a line Yes if the tree is unique, or No if not. Then print in the next line the inorder traversal sequence of the corresponding binary tree. If the solution is not unique, any answer would do. It is guaranteed that at least one solution exists. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input 1:

7
1 2 3 4 6 7 5
2 6 7 4 5 3 1

Sample Output 1:

Yes
2 1 6 4 7 3 5

Sample Input 2:

4
1 2 3 4
2 4 3 1

Sample Output 2:

No
2 1 3 4

题目描述：提供一个二叉树的所有节点值(值为正整数)。唯一的二叉树可以由后序遍历和中序遍历得到，也可以由先序遍历和中序遍历得到。但是，如果只给出先序遍历和后序遍历，得到的二叉树有可能是不唯一的，则他的中序遍历也有可能不唯一。题目给出一对先序遍历和后序遍历数组，求出是否能得到唯一的二叉树，可以则输出Yes，否则输出No。最后一行输出中序遍历，若有多个，输出一个即可。

解题思路：设置一个flag标志，判断这个二叉树是否唯一。

用样例分析一下：

prel、prer分别是pre数组的左右索引边界值；postl、postr分别是post数组的左右索引边界值。

一开始prel=0，prer=6，postl=0，postr=6

当pre[prel]等于post[postr]，==>pre[0]=1，post[6]=1，一开始就相等了，可以知道，这个值就是根节点的值。题目要求输出中序遍历，输出顺序是左、中(根)、右。当得到中(根)时，不能直接输出，要先求出左，才能将中(根)输出。后续的过程看代码，已加上注释。

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> pre, post, inorder;
bool flag = true;
void get_inorder(int prel, int prer, int postl, int postr){
	if(prel==prer){
		inorder.push_back(pre[prel]);
		return ;
	}
	int i=prel, j=postr-1, k;
	if(pre[prel]==post[postr]){//发现中间结点 
		while(i<=prer&&j>=0&&pre[i]!=post[j]) i++;//求出右子节点在pre数组的位置
		k = i-prel-1;//得到左子树的结点个数
		if(k>0){
			get_inorder(prel+1,i-1,postl,postl+k-1);//左子树进入递归，相应的数组范围会改变
		}
		else flag = false;
	}
	inorder.push_back(post[postr]);
	get_inorder(i,prer,postl+k,postr-1);//右子树进入递归
}
int main()
{
	scanf("%d", &n);
	pre.resize(n);
	post.resize(n);
	for(int i=0; i<n; i++) scanf("%d", &pre[i]);
	for(int i=0; i<n; i++) scanf("%d", &post[i]);
	get_inorder(0,n-1,0,n-1);
	if(flag) printf("Yes\n");
	else printf("No\n");
	for(int i=0; i<inorder.size(); i++){
		if(i) printf(" ");
		printf("%d", inorder[i]);
	}
	printf("\n");//没有这个就格式错误，0分bug
	return 0;
}