PTA:根据后序和中序遍历输出先序遍历 (20 分)

题目详情：

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。

输入格式:

第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式:

在一行中输出Preorder: 以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。

输入样例:

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

结尾无空行

输出样例:

Preorder: 4 1 3 2 6 5 7

结尾无空行

作者：DS课程组；单位：浙江大学；代码长度限制：16 KB；时间限制：400 ms；内存限制：64 MB

已知中序和后序遍历，求前序遍历。如果是笔算，正常思路就是先从后序遍历倒着读，找到后序结果的最后一个（根），然后可以再中序中找到该节点，分为左右两个部分为左右子树，再重复上述操作。这是一个递归的过程，找到左右子树的时候就可以递归求解了。

我写的一个打印前序函数为：void print_front(int *l,int *m,int p=n-1)

l为后序数组，m为中序数组，p为根结点的位置

下面只要在中序中找到l[p]的位置，然后根据这个位置复制出左边的中序和后序数组L1[n],L2[n]，以及右边的R1[n],R2[n].传入递归即可。在这个过程中要注意复制的位置。

Code:

#include<iostream>
using namespace std;
int n;
int find(int *a,int x)  //再数组中找x（肯定可以找到）
{
	for(int i=0;i<n;i++)
	if(a[i]==x) return i;
}
void print_front(int *l,int *m,int p=n-1) //打印前序
{
	if(p>=0){
		cout<<" "<<l[p];
		int r=find(m,l[p]); //中序中找到根节点
		int L1[n],R1[n],L2[n],R2[n];
		for(int i=0;i<r;i++){ //左边的都是0~r-1
			L1[i]=l[i];
			L2[i]=m[i];
		}
		for(int i=r,j=0;i<p;i++,j++){ //右边的两个不一样，分别复制
			R1[j]=l[i];
		}
		for(int i=r+1,j=0;i<=p;i++,j++){
			R2[j]=m[i];
		}
		print_front(L1,L2,r-1); //递归打印
		print_front(R1,R2,p-r-1);
	}
}
int main()
{
	cin>>n;
	int last[n],mid[n];
	for(int i=0;i<n;i++) cin>>last[i]; //后序
	for(int i=0;i<n;i++) cin>>mid[i]; //中序
	cout<<"Preorder:";
	print_front(last,mid); 
	return 0;
}

结果：

按照这个思路就AC了。我看到dalao用string的性质，直接取子串，就省去了繁琐的数组复制。当然是对于读入后序中序时就是字符串更适用，而本题读的是数。

不过我还是强行用string又写了一个：

#include<iostream>
#include<string>
using namespace std;
void print_front(string l,string m) //l为后序字串，m为中序
{
	if(l.size()>0){
		int ch=l[l.size()-1]; //找到最后一个
		cout<<" "<<ch; //这里输出的是ascll码，字符无意义
		int k=m.find(ch);
		print_front(l.substr(0,k),m.substr(0,k)); //调用substr直接划分
		print_front(l.substr(k,l.size()-k-1),m.substr(k+1)); 
	}
}
int main()
{
	int n;
	cin>>n;
	string last,mid;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		last.push_back(x); //不管字符是什么，输出只关心ascll码，string只是个工具
	}
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		mid.push_back(x);
	}
	cout<<"Preorder:";
	print_front(last,mid);
	return 0;
}

结果：

注意：如果给的数据量比较大，不要用字符串处理，毕竟ascll值最大为255.