本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。
输入格式:
第一行给出正整数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通过截图：
思路分析：
起初看到后序遍历和中序遍历，第一想法是用这个数组创建一棵树，但是考虑到我之前写过的创建树的代码不接受这样的输入（以前的问题），因此开始考虑能不能通过我们人类的思维方式，来想一个能用后序和中序推出先序的算法（相信三者转换是有规律的，因为我们做那种简答题或者选择题，也是按照一定规律推到树，然后写出来的）。
例如：
要知道，后序（Post）遍历是LRV，中序（Min）遍历是LVR，先序（Pre）遍历是VLR（V 根节点，L 左子树结点，R 右子树结点）。下面写一下该题的图示：
其中，我们不难发现， Post的最后一个字符是根节点（Post的最后一个，Pre的第一个），该结点下面的左子树的根节点是第二个我们要输出的，以此类推。
人类手绘创建的树如下：
我们在手绘树的时候，发现，在中序遍历数组中所找到根节点，左边的是左子树，右边的是右子树，即 (1((2)3))4((5)6(7)) 红色括号为右子树，深绿为左子树，准备好之后，明白我们要找到根（root），子树一个括号中的第一个元素位置（start），子树括号最后一个元素位置（fin）。
树大概是比较推荐用递归来写，所以我选择了用递归来写，之后疯狂debug折磨自己。因为非递归的思路不是很清楚，我们下面决定用递归来写（之前文章内容就没写过非递归的遍历检查，所以这里行进困难），递归的思路是先序遍历寻找，找到本次操作的根节点后，在中序中寻找此结点，记录下此节点的下标位置，作为在左子树或是右子树的位置线索。
位置线索思考与整理：
画图表，找到相关联的数字线索，做出数学公式，此处普适公式寻找比较困难，从特例开始（普朗克也是这样发现能量子的），此处思路参考了：已知后序与中序输出前序（先序） – 柳婼 の blog (liuchuo.net)https://www.liuchuo.net/archives/2090 此思路表格展示为【表头第一列为相对于其父母结点的位置，其后数字个数为所在层数+位置（左子树为1，右子树为2），root，start，fin上面已有赘述，i为root元素在中序遍历中的下标位置，n为此结点的值（最后两行是博主在写时没有列出来的，尤其是start和fin，因此博主有蒙对的嫌疑！！不过后来列表的时候居然完美吻合）】：
因此，经过观察和统计，整理（Main 0 -> Left 1，Right 1.2 -> Left 1.2.1）左子树的计算公式为 ： ，，；
整理（Main 0 -> Right 2，Left 1 ->Right 1.2 ）右子树的计算公式为：，，
这样，我们就明白了整体流程（当然，博主是边想边写的，这块debug了好长时间） ，现在我们要将它写成代码。文章来源：https://www.toymoban.com/news/detail-773315.html
代码整理（递归）：
//
// Created by DDD on 2023/11/20.
//
#include <stdio.h>
void makePre(int post[], int min[], int root, int fin, int start){
if((fin <= start)||(root<0))
return;
int i;
int head = post[root];
for(i=start; i<fin;i++) {
if (min[i] == head) {
break;
}
}
printf(" %d",head); //此处处理了题目中输出要求
makePre(post,min,root-fin+i,i,start); //左子树
makePre(post,min,root-1,fin,i+1); //右子树
}
int main(){
int num;
scanf("%d",&num);
int post[num]; //后序
int min[num]; //中序
for(int i=0; i<num;i++){
scanf("%d",&post[i]);
}
for(int i=0; i<num;i++){
scanf("%d",&min[i]);
}
printf("Preorder:");
makePre(post,min,num - 1,num,0);
}return 0; //归去来文章来源地址https://www.toymoban.com/news/detail-773315.html
到了这里，关于7-1 根据后序和中序遍历输出先序遍历 (PTA-数据结构)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
