二叉树，已知中序和后序求先序 递归思想
[NOIP2001]求先序排列
https://ac.nowcoder.com/acm/contest/19859/N
先序从根开始遍历，且是从左到右对子树进行遍历，所以左支树放在前面，右支树放在后面按顺序输出各个子树的根，对函数先找出根的位置并输出
左支树中：在中序中，第一个节点到根的距离为根的下标；在后序中，第一个节点到根的距离同样是根的下标
右支树中：在中序中，根右边的所有节点满足右支树：而后序中，中序根的位置便是后序右支树开始的下标，长度为：后序长度-1-中序中根的位置
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void Findroot(string mid,string end)
{
int len2=end.size();//后序的长度
if(mid.size()>0)//表示树中的节点大于0
{
char ch=end[end.size()-1];//找树的根
cout<<ch;
int pos=mid.find(ch);//求出树的根对应的下标
Findroot(mid.substr(0,pos),end.substr(0,pos));//左支树
Findroot(mid.substr(pos+1),end.substr(pos,len2-1-pos));//右支树
}
return;
}
int main()
{
string mid,end;
cin>>mid>>end; //分别输入中序和后序
Findroot(mid,end);
return 0;
}
美的集团开奖6人在聊