7-11 玩转二叉树(中序遍历和先序遍历建树)

    科技2024-08-19  24

    #include<bits/stdc++.h> using namespace std; int n; const int N=35; int z[N],x[N]; int ls[N],rs[N]; int num; void solve(int a,int b,int c,int d){ int t=x[c]; int i; for(i=a;i<=b;i++){ if(z[i]==t){ break; } } if(i==a){ if(c+1<=d){ rs[t]=x[c+1]; solve(a+1,b,c+1,d); } } else if(i==b){ if(c+1<=d){ ls[t]=x[c+1]; solve(a,b-1,c+1,d); } } else{ if(c+1<=n){ ls[t]=x[c+1]; solve(a,i-1,c+1,c+i-a); } if(c+i-a+1<=n){ rs[t]=x[c+i-a+1]; solve(i+1,b,c+i-a+1,d); } } } void bfs(int x){ queue<int> q; q.push(x); //int g=ls[x]; //ls[x]=rs[x]; //rs[x]=g; while(q.size()){ num++; int t=q.front(); q.pop(); //g=ls[t]; //ls[t]=rs[t]; //rs[t]=g; if(num==n) printf("%d\n",t); else printf("%d ",t); if(rs[t]) q.push(rs[t]); if(ls[t]) q.push(ls[t]); } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&z[i]); for(int i=1;i<=n;i++) scanf("%d",&x[i]); int root=x[1]; solve(1,n,1,n); bfs(root); return 0; }

     

    Processed: 0.011, SQL: 8