这个代码为了理清思路，很多地方写的有些亢余。
首先要明确建树过程，先序遍历的第一个结点一定是根节点，在中序遍历中找到这个结点，那么他的左边就是他的左子树，右边就是他的右子树，只要找到子树的范围，就可以递归调用。
要明确他的翻转过程，其实就是求出层序遍历后，将他每层倒着输出，所以总着来说就知识一个已知先序中序遍历，求层序遍历的问题。
这里用tr[i]保存每个位置上的结点的值，如果为0，则表示该位置为空。
感谢数据没有30层极限数据，能让这种方法过掉。
代码：
#include<iostream>
#include<vector>
using namespace std;
const int N = 1000005;
int tr[N];
int mid[N],pre[N];
int n;
vector<int>ans;
int Find(int x)
{
for(int i=1;i<=n;i++)
if(mid[i]==x) return i;
}
void build(int l1,int r1,int l2,int r2,int root)
{
if(l1>r1) return;
tr[root]=pre[l2];
int pos = Find(pre[l2]);
int lnum = pos-l1;
int rnum = r1-pos;
build(l1,pos-1,l2+1,l2+lnum,root<<1);
build(pos+1,r1,l2+lnum+1,r2,root<<1|1);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>mid[i];
for(int i=1;i<=n;i++) cin>>pre[i];
build(1,n,1,n,1);
//for(int i=1;i<=n;i++) cout<<tr[i]<<" ";
for(int i=1;i*2-1<N;i*=2)
{
int bg=2*i-1;
for(int j=bg;j>=i;j--)
{
if(tr[j]) ans.push_back(tr[j]);
}
}
for(auto it = ans.begin();it!=ans.end();it++)
{
if(it==ans.begin()) cout<<*it;
else cout<<" "<<*it;
}
return 0;
}
文章为作者独立观点，不代表 股票程序化软件自动交易接口观点
相关文章
股民评论