不能用线段树开4N空间,因为深度并不确定,最差情况肯定爆内存
解决办法就是反过来建树,根节点->右子树->左子树,建树的过程用stack把结果存下来
#include<bits/stdc++.h> #define endl '\n' #define _for(i,a,b) for(int i=a;i<b;i++) using namespace std; const int N = 1055; typedef long long ll; int pre[N],in[N]; stack<int> Sta; void Build( int s1,int e1,int s2,int e2 ){//s1e1是前序的,s2e2是中序的 Sta.push( pre[s1] ); int cnt = 0; _for(i,s2,e2+1){ if( in[i] == pre[s1] ) break; cnt++; } if( s1+cnt+1<=e1 ) Build( s1+cnt+1,e1,s2+cnt+1,e2 ); if( s1+1<=s1+cnt ) Build( s1+1,s1+cnt,s2,s2+cnt-1 ); } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n; while(cin>>n){ _for(i,1,n+1) cin>>pre[i]; _for(i,1,n+1) cin>>in[i]; Build( 1,n,1,n ); cout<<Sta.top(); Sta.pop(); while( Sta.size() ){ cout<<' '<<Sta.top(); Sta.pop(); } cout<<endl; } return 0; }
原文链接: https://www.cnblogs.com/SunChuangYu/p/12488775.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/335215
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!