[数据结构与算法]【二叉树】根据后续和中序遍历输出前序遍历 [建树+非建树做法]

F . 案例 4-1.1：根据后续和中序遍历输出前序遍历
Description
本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。

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

Output
在一行中输出Preorder: 以及该树的先序遍历结果。

Samples
Input 复制
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
Output
Preorder: 4 1 3 2 6 5 7

先贴一篇dalao模拟的题解

整体思路：由后序遍历找到根节点，然后在中序遍历中找到分割点，然后递归遍历左右子树即可。

非建树做法：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int post[N],mid[N];
void Pre(int *post,int *mid,int l){
	if(l<=0) return ;
	cout<<" "<<post[l-1];
	int i;//定义左子树的长度
	for(i=0;i<l;i++) if(mid[i]==post[l-1]) break;//在中序遍历中找到分割点
	Pre(post,mid,i);//由于我们定义根节点为post[l-1]所以这里我们传长度i
	Pre(post+i,mid+i+1,l-i-1);//由于左子树长度为i那么去下刚输出的根节点就是l-i-1
}
/*
7
2 3 1 5 7 6 4 //post
1 2 3 4 5 6 7 //mid

4 1 3 2 6 5 7
*/
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++) cin>>post[i];
	for(int i=0;i<n;i++) cin>>mid[i];
	
	cout<<"Preorder:";
	Pre(post,mid,n);
	
	return 0;
}

建议读者看懂上述数组模拟，那下面的呢建树做法就迎刃而解了

建树做法：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int post[N],mid[N];
struct Node{
	int val;
	Node *lch,*rch;
};
Node *creat(int *post,int *mid,int l){
	if(l<=0) return NULL;
	Node *root=new Node;
	root->val=post[l-1];
	int *p;
	for(p=mid;p!=NULL;p++) if(*p==post[l-1]) break;
	int i=p-mid;
	root->lch=creat(post,mid,i);
	root->rch=creat(post+i,mid+i+1,l-i-1);
	return root;
}
void print(Node *root){
	if(root==NULL) return ;
	printf(" %d",root->val);
 	print(root->lch);
	print(root->rch);
	
	//cout<<" "<<*root;
}
 
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++) cin>>post[i];
	for(int i=0;i<n;i++) cin>>mid[i];
	Node *root=new Node;
	root=creat(post,mid,n);
	cout<<"Preorder:";
	print(root);
	
	return 0;
}
/*
7
2 3 1 5 7 6 4 //post
1 2 3 4 5 6 7 //mid

4 1 3 2 6 5 7
*/