はなたの日記

プログラミング(C言語)の勉強をしています。超初心者です。

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;
	
}

なんで昔解けたんだろうな。