ALDS1_7_D Reconstruction of a Tree
問題
木の復元 | アルゴリズムとデータ構造 | Aizu Online Judge
ある木について、preorderとinorderで得られた情報から木を構築し、postorderを求める問題です。
以下のページが分かり易かったです。
データ構造 巡回結果からの木の構築 Tree - Reconstruction of a Tree - ikap
理屈は分かったのですが、結局昔自分で実装したのを見ながらの実装となりました。
#include<stdio.h> #define N 41 typedef struct node{ int L_id; int R_id; }node; node c[N]; int a[N]; int b[N]; int cnt=0; void postorder(int root,int n){ if(c[root].L_id!=-1) postorder(c[root].L_id,n); if(c[root].R_id!=-1) postorder(c[root].R_id,n); if(cnt<n-1) printf("%d ",root); else printf("%d\n",root); cnt++; return; } int reconst(int start,int last,int n){ if(start==last) return b[start]; else if(start > last) return -1; else { for(int i=1;i<=n;i++){ for(int j=start;j<=last;j++){ if(a[i]==b[j]){ c[a[i]].L_id=reconst(start,j-1,n); c[a[i]].R_id=reconst(j+1,last,n); return a[i]; } } } } } int main(){ int n,i; int root; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++) scanf("%d",&b[i]); for(i=1;i<=n;i++){ c[i].L_id=-1; c[i].R_id=-1; } root=reconst(1,n,n); postorder(root,n); return 0; }
なんで昔解けたんだろうな。