一、题目大意
题目链接：https://pintia.cn/problem-sets/434/problems/6101
本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。
输入格式:
第一行给出正整数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结尾无空行
二、ac代码
#include <bits/stdc++.h> using namespace std; void pre(int*in,int*post,int n) { if (n<=0) return; int root=post[n-1]; int i=0; for (;i<n;i++) { if (in[i]==root) break; } cout<<" "<<root; pre(in,post,i); pre(in+i+1,post+i,n-i-1); } int main(void) { int n; cin>>n; int in[1005],post[1005]; for (int i=0;i<n;i++) cin>>post[i]; for (int i=0;i<n;i++) cin>>in[i]; cout<<"Preorder:"; pre(in,post,n); return 0; }
完全不知道怎么做，在看了大佬的基础上才勉强ac
https://blog.csdn.net/weixin_42449444/article/details/85331082
第一次见到这种思路，数据结构实在学的太差了- -
总体思路就是后续遍历的最后一项是根，然后可以从中序遍历中判断左右树，从而递归
代码实现总体和前序遍历差不多，先输出从中序遍历中找到的根，再递归左子树右子树
这里如果定义全局数组，函数里传下标应该也是可以实现的，因为平时很少看到传数组所以就写一下0 0
递归的时候传递的参数是比较重要的，左子树为原来两个数组最左到根在中序遍历中的下标为止
右子树为根在中序遍历的下标开始到两个数组结尾
中序遍历：（左子树）+根+（右子树）
后序遍历：（左子树）+（右子树）+根
由上述两行可见，右子树递归时前两个参数为何差一
感谢所有大佬的思路和代码！
peace